Given a linked list, remove the n-th node from the end of list and return its head.
Example:
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.
Two pass
In the first pass, we will find out the length of the linked list. Then in the second pass, we will locate the len(linked_list) – n th element and remove it.
Corner cases
singleton linked list and n = 1
The new linked list should be empty
Remove the head with n = len(linked list)
Remove the end with n = 0
We can solve all these corner case by the use of dummy head.
Code
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
Two pass
"""
l_len = 0
dummy_head = ListNode(1)
dummy_head = head
while dummy_head:
l_len += 1
dummy_head = dummy_head.next
dummy_head = ListNode(2)
dummy_head.next = head
node_ptr = dummy_head
#go forward to the node before the removed node
for i in range(l_len - n):
node_ptr = node_ptr.next
next_ptr = node_ptr.next.next
node_ptr.next = next_ptr
return dummy_head.next
We use the first loop to determine the length of the linked list. Then use a second for loop to find to pointer that points to the node that’s before the to-be-removed node. We use dummy head whose next pointer points to the head to make it simply
use dummy head
An example:
D -> 1 -> 2 -> None
We set node_ptr, which points to the node before the to_be_removed node, to dummy head.
linked_list_len = 2
resolve corner cases of removing the head
if we want to remove the head, we need to remove the second node from the end. n = 2. In our code, the for loop will not execute, leaving the node_ptr = dummy_head. Without dummy head, we need to create a new node that serves as the node before head.
Simplify counting
We know the nth node from the end is also the linked_list_len – n – 1 th node.
If we use dummy head, the nth node from the end would also be linked_list_len – n th node.
One pass
We will use two pointer to keep track both the current pointer iterating the linked list and also where the n + 1th element before the current pointer is. When the iteration finishes, the slow pointer will point to the n + 1 th element before the end, then we will remove the element next to the slower pointer and point the slower pointer’s next to the next of the removed node.
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
one pass
"""
dummy_head = ListNode(1)
dummy_head.next = head
fast = dummy_head
slow = dummy_head
for i in range(n + 1):
fast = fast.next
while fast:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return dummy_head.next