Given a linked list, remove the n-th node from the end of list and return its head.
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.
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.
The new linked list should be empty
Remove the end with n = 0
We can solve all these corner case by the use of dummy head.
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
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.
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.
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