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:
[1, 105].1 <= Node.val <= 105This approach involves reversing the linked list and using a stack to maintain the maximum values encountered so far. This allows us to easily determine which nodes have a greater value to their right.
The code defines a function removeNodes that takes a singly linked list and removes nodes that have a node with a greater value to their right. It uses a stack to keep track of potential candidates for the resulting list, reconstructing the list after determining the correct elements.
Java
Time Complexity: O(n), where n is the number of nodes in the linked list since each node is processed twice.
Space Complexity: O(n), due to the use of an additional stack to store nodes.
This approach uses recursion to traverse the list and solve the problem recursively by backtracking from the end of the list to the start.
The recursive solution traverses to the end of the list, then checks if the current node should be part of the result or skipped based on the value comparison of its next node, ensuring that nodes with greater values are prioritized.
JavaScript
Time Complexity: O(n) - as each node is visited exactly once.
Space Complexity: O(n) - due to recursive stack space used during function calls.
| Approach | Complexity |
|---|---|
| Approach 1: Reverse Traversal Using a Stack | Time Complexity: O(n), where n is the number of nodes in the linked list since each node is processed twice. |
| Approach 2: Recursion and Backtracking | Time Complexity: O(n) - as each node is visited exactly once. |
Remove Nth Node from End of List - Oracle Interview Question - Leetcode 19 • NeetCode • 224,471 views views
Watch 9 more video solutions →Practice Remove Nodes From Linked List with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor