Question

2487. Remove Nodes From Linked List

中文文档

Description

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

Solutions

Solution 1: Monotonic Stack Simulation

We can first store the node values of the linked list into an array $nums$. Then, we traverse the array $nums$, maintaining a stack $stk$ that is monotonically decreasing from the bottom to the top. If the current element is larger than the top element of the stack, we pop the top element of the stack until the current element is less than or equal to the top element, and then we push the current element into the stack.

Finally, we construct the resulting linked list from the bottom to the top of the stack, which is the answer.

The time complexity is $O(n)$, and the space complexity is $O(n)$, where $n$ is the length of the linked list.

We can also directly traverse the linked list without using the array $nums$, maintaining a stack $stk$ that is monotonically decreasing from the bottom to the top. If the current element is larger than the top element of the stack, we pop the top element of the stack until the current element is less than or equal to the top element. Then, if the stack is not empty, we set the $next$ pointer of the top element of the stack to the current element. Otherwise, we set the $next$ pointer of the dummy head node of the answer linked list to the current element. Finally, we push the current element into the stack and continue to traverse the linked list.

After the traversal, we return the $next$ pointer of the dummy head node as the answer.

The time complexity is $O(n)$, and the space complexity is $O(n)$, where $n$ is the length of the linked list.

# Definition for singly-linked list.
# class ListNode:
#   def __init__(self, val=0, next=None):
#     self.val = val
#     self.next = next
class Solution:
  def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
    nums = []
    while head:
      nums.append(head.val)
      head = head.next
    stk = []
    for v in nums:
      while stk and stk[-1] < v:
        stk.pop()
      stk.append(v)
    dummy = ListNode()
    head = dummy
    for v in stk:
      head.next = ListNode(v)
      head = head.next
    return dummy.next

/**
 * 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) {
    List<Integer> nums = new ArrayList<>();
    while (head != null) {
      nums.add(head.val);
      head = head.next;
    }
    Deque<Integer> stk = new ArrayDeque<>();
    for (int v : nums) {
      while (!stk.isEmpty() && stk.peekLast() < v) {
        stk.pollLast();
      }
      stk.offerLast(v);
    }
    ListNode dummy = new ListNode();
    head = dummy;
    while (!stk.isEmpty()) {
      head.next = new ListNode(stk.pollFirst());
      head = head.next;
    }
    return dummy.next;
  }
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *   int val;
 *   ListNode *next;
 *   ListNode() : val(0), next(nullptr) {}
 *   ListNode(int x) : val(x), next(nullptr) {}
 *   ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
  ListNode* removeNodes(ListNode* head) {
    vector<int> nums;
    while (head) {
      nums.emplace_back(head->val);
      head = head->next;
    }
    vector<int> stk;
    for (int v : nums) {
      while (!stk.empty() && stk.back() < v) {
        stk.pop_back();
      }
      stk.push_back(v);
    }
    ListNode* dummy = new ListNode();
    head = dummy;
    for (int v : stk) {
      head->next = new ListNode(v);
      head = head->next;
    }
    return dummy->next;
  }
};

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *   Val int
 *   Next *ListNode
 * }
 */
func removeNodes(head *ListNode) *ListNode {
  nums := []int{}
  for head != nil {
    nums = append(nums, head.Val)
    head = head.Next
  }
  stk := []int{}
  for _, v := range nums {
    for len(stk) > 0 && stk[len(stk)-1] < v {
      stk = stk[:len(stk)-1]
    }
    stk = append(stk, v)
  }
  dummy := &ListNode{}
  head = dummy
  for _, v := range stk {
    head.Next = &ListNode{Val: v}
    head = head.Next
  }
  return dummy.Next
}

/**
 * Definition for singly-linked list.
 * class ListNode {
 *   val: number
 *   next: ListNode | null
 *   constructor(val?: number, next?: ListNode | null) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 *   }
 * }
 */

function removeNodes(head: ListNode | null): ListNode | null {
  const nums = [];
  for (; head; head = head.next) {
    nums.push(head.val);
  }
  const stk: number[] = [];
  for (const v of nums) {
    while (stk.length && stk.at(-1)! < v) {
      stk.pop();
    }
    stk.push(v);
  }
  const dummy = new ListNode();
  head = dummy;
  for (const v of stk) {
    head.next = new ListNode(v);
    head = head.next;
  }
  return dummy.next;
}

Solution 2

# Definition for singly-linked list.
# class ListNode:
#   def __init__(self, val=0, next=None):
#     self.val = val
#     self.next = next
class Solution:
  def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
    dummy = ListNode(inf, head)
    cur = head
    stk = [dummy]
    while cur:
      while stk[-1].val < cur.val:
        stk.pop()
      stk[-1].next = cur
      stk.append(cur)
      cur = cur.next
    return dummy.next

/**
 * 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) {
    ListNode dummy = new ListNode(1 << 30, head);
    Deque<ListNode> stk = new ArrayDeque<>();
    stk.offerLast(dummy);
    for (ListNode cur = head; cur != null; cur = cur.next) {
      while (stk.peekLast().val < cur.val) {
        stk.pollLast();
      }
      stk.peekLast().next = cur;
      stk.offerLast(cur);
    }
    return dummy.next;
  }
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *   int val;
 *   ListNode *next;
 *   ListNode() : val(0), next(nullptr) {}
 *   ListNode(int x) : val(x), next(nullptr) {}
 *   ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
  ListNode* removeNodes(ListNode* head) {
    ListNode* dummy = new ListNode(1e9, head);
    ListNode* cur = head;
    vector<ListNode*> stk = {dummy};
    for (ListNode* cur = head; cur; cur = cur->next) {
      while (stk.back()->val < cur->val) {
        stk.pop_back();
      }
      stk.back()->next = cur;
      stk.push_back(cur);
    }
    return dummy->next;
  }
};

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *   Val int
 *   Next *ListNode
 * }
 */
func removeNodes(head *ListNode) *ListNode {
  dummy := &ListNode{1 << 30, head}
  stk := []*ListNode{dummy}
  for cur := head; cur != nil; cur = cur.Next {
    for stk[len(stk)-1].Val < cur.Val {
      stk = stk[:len(stk)-1]
    }
    stk[len(stk)-1].Next = cur
    stk = append(stk, cur)
  }
  return dummy.Next
}

/**
 * Definition for singly-linked list.
 * class ListNode {
 *   val: number
 *   next: ListNode | null
 *   constructor(val?: number, next?: ListNode | null) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 *   }
 * }
 */

function removeNodes(head: ListNode | null): ListNode | null {
  const dummy = new ListNode(Infinity, head);
  const stk: ListNode[] = [dummy];
  for (let cur = head; cur; cur = cur.next) {
    while (stk.at(-1)!.val < cur.val) {
      stk.pop();
    }
    stk.at(-1)!.next = cur;
    stk.push(cur);
  }
  return dummy.next;
}