Remove Nth Node From End of List
DESCRIPTION (credit Leetcode.com)
Given a reference head of type ListNode that is the head node of a singly linked list and an integer n, write a function that removes the n-th node from the end of the list and returns the head of the modified list.
Note: n is guaranteed to be between 1 and the length of the list. If n is the length of the list, the head of the list should be removed.
EXAMPLES
Example 1:
input:
output:
Explanation: The 2nd to last node is removed from the list.
Example 2:
input:
output:
Explanation: The 5th to last node is the head node, so it is removed.
Solutions
In order to remove the n-th node from the end of the list, we first need to locate the node right before it.
For example, if our list is [5, 4, 3, 2, 1] and n = 2, then we need to remove the 2nd node from the end with value 2. In order to do so, we first need to locate the node right before it, with value 3.
If we have a pointer to that node current, we can delete node 2 by setting current.next = current.next.next, which removes node 2 from the list (as no nodes point to it).
Here are a 3 solutions to this problem, each of which approach the problem of locating the node right before the n-th node from the end in a different way.
1. Find the Length of the List
The first approach is to traverse the list to find its length. Once we know the length of the list, we can find the node right before the n-th node from the end by traversing length - n - 1 nodes from the head.
def removeNthFromEnd(head, n):length = 0current = headwhile current:length += 1current = current.next# special case: removing headif n == length:return head.nextcurrent = headfor _ in range(length - n - 1):current = current.nextcurrent.next = current.next.nextreturn head
We have to handle the special case when n is equal to the length of the list, which requires removing the head node. This needs to be handled separately because head does not have a node right before it to locate. Instead, when n == length, we can remove the head node by returning head.next directly.
Time Complexity: O(N), where N is the number of nodes in the list. We traverse the list once to find the length of the list, and another time to find the node right before the n-th node from the end. Both traversals take O(N) time.
Space Complexity: O(1). We only use a constant amount of extra space for the pointers, regardless of the number of nodes in the list.
2. Use Two Pointers
Instead of traversing the list once to find its length, we can use two pointers, fast and slow that both start at head. To start, fast advances n nodes ahead of slow. Then both pointers advance one node at a time until fast reaches the last node in the list.
At this point, slow will point to the node right before the n-th node from the end, and we can remove the n-th node by setting slow.next = slow.next.next.
def removeNthFromEnd(head, n):fast = slow = headfor _ in range(n):fast = fast.next# special case: removing headif not fast:return head.nextwhile fast.next:fast = fast.nextslow = slow.nextslow.next = slow.next.nextreturn head
Like before, we have to handle the special case when n is equal to the length of the list. Since we don't know the length of the list, we can't detect this case by comparing the two values directly. Instead, if fast is None after advancing n nodes, we know that n is equal to the length of the list, and we can remove the head node by returning head.next directly.
def removeNthFromEnd(head, n):fast = slow = headfor _ in range(n):fast = fast.next# special case: removing headif not fast:return head.nextwhile fast.next:fast = fast.nextslow = slow.nextslow.next = slow.next.nextreturn head
Time Complexity: O(N), where N is the number of nodes in the list. The fast pointer traverses the entire list once, taking O(N) time. The slow pointer traverses n nodes after the fast pointer, where n is the input parameter. This takes O(N) time in the worst case.
Space Complexity: O(1). We only use a constant amount of extra space for the pointers, regardless of the number of nodes in the list.
3. Dummy Node
In the two above approaches, we need special logic to handle removing the head node because the head node does not have a node right before it to locate.
We can avoid this special case by introducing a dummy node that points to the head of the list. The dummy node allows us to treat every node, including the head, as if it has a preceding node. With the dummy node established, we can again use the two-pointer approach to find the node right before the n-th node from the end.
def removeNthFromEnd(head, n):dummy = ListNode(0)dummy.next = headfast, slow = dummy, dummyfor _ in range(n):fast = fast.nextwhile fast.next:fast = fast.nextslow = slow.next# remove nth node from endslow.next = slow.next.nextreturn dummy.next
Both the fast and slow pointers start at the dummy node, and like before, fast advances n nodes ahead of slow. Then both pointers advance one node at a time until fast reaches the last node in the list.
def removeNthFromEnd(head, n):dummy = ListNode(0)dummy.next = headfast, slow = dummy, dummyfor _ in range(n):fast = fast.nextwhile fast.next:fast = fast.nextslow = slow.next# remove nth node from endslow.next = slow.next.nextreturn dummy.next
At this point, slow will point to the node right before the n-th node from the end, and we can remove the n-th node by setting slow.next = slow.next.next, and return dummy.next as the head of the modified list.
def removeNthFromEnd(head, n):dummy = ListNode(0)dummy.next = headfast, slow = dummy, dummyfor _ in range(n):fast = fast.nextwhile fast.next:fast = fast.nextslow = slow.next# remove nth node from endslow.next = slow.next.nextreturn dummy.next
Removing the Head Node
With the dummy node, when n is equal to the length of the list, slow still points to the dummy node after both the fast and slow pointers finish advancing.
Now, we can remove the head node by setting slow.next = slow.next.next, and return slow.next as the head of the modified list - which is the exact same logic as removing any other node!
def removeNthFromEnd(head, n):dummy = ListNode(0)dummy.next = headfast, slow = dummy, dummyfor _ in range(n):fast = fast.nextwhile fast.next:fast = fast.nextslow = slow.next# remove nth node from endslow.next = slow.next.nextreturn dummy.next
Code
def removeNthFromEnd(head, n):dummy = ListNode(0)dummy.next = headfast, slow = dummy, dummyfor _ in range(n):fast = fast.nextwhile fast.next:fast = fast.nextslow = slow.next# remove nth node from endslow.next = slow.next.nextreturn dummy.next
Complexity Analysis
Time Complexity: The time complexity of the dummy node approach is O(N), where N is the number of nodes in the list. The fast pointer always traverses the entire list once, taking O(N) time. At worst, when n = 1, the slow pointer traverses to the 2nd to last node, which also takes O(N) time. Removing the n-th node from the end takes O(1) time, so the overall time complexity is O(N).
Space Complexity: The space complexity of the dummy node approach is O(1). We only use a constant amount of extra space for the pointers and allocate one dummy node, regardless of the number of nodes in the list.
Loading comments...