You are given the head of a linked list.
Remove every node which has a node with a greater value anywhere to the right side of it.
Return the head of the modified linked list.
Example 1:
Input: head = [5,2,13,3,8]
Output: [13,8]
Explanation: The nodes that should be removed are 5, 2 and 3.
- Node 13 is to the right of node 5.
- Node 13 is to the right of node 2.
- Node 8 is to the right of node 3.
Example 2:
Input: head = [1,1,1,1]
Output: [1,1,1,1]
Explanation: Every node has value 1, so no nodes are removed.
Constraints:
The number of the nodes in the given list is in the range [1, 105].
1 <= Node.val <= 105
从链表中移除节点。
给你一个链表的头节点 head 。 移除每个右侧有一个更大数值的节点。 返回修改后链表的头节点 head 。
思路
根据题意,如果某个 node 的右侧有一个比他 val 更大的 node,需要把这个 node 删除。那么这里我们可以反过来思考,如果我们从右往左遍历整个链表,我们可以先把第一个节点的 val 当做最大值,记为 max,再往左遍历的时候,如果当前节点值比 max 小,则把当前节点移除;否则把当前节点的节点值记为 max,继续往左遍历。这样做的好处是,我们只需要遍历一次链表,就可以把所有需要删除的节点都删除掉。不过我们需要将 input 链表整个反转一次,遍历一次,再反转回去。
复杂度
时间O(n)
空间O(1)
代码
Java实现
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeNodes(ListNode head) {
// corner case
if (head == null || head.next == null) {
return head;
}
// normal case
head = reverse(head);
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode cur = dummy;
int max = 0;
while (cur.next != null) {
if (cur.next.val < max) {
cur.next = cur.next.next;
} else {
max = cur.next.val;
cur = cur.next;
}
}
head = reverse(head);
return head;
}
private ListNode reverse(ListNode head) {
ListNode cur = head;
ListNode pre = null;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}
标签:node,head,ListNode,cur,val,2487,List,Remove,next
From: https://www.cnblogs.com/cnoodle/p/18177028