Two pointers and Linked List

19. Remove Nth Node From End of List

The two-pass solution

The two-pass solution is relatively easier. We traverse the list and find the total number of nodes for this list say N. Then the last n element will be the first N- n

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(-1)
        dummy.next = head
        node = dummy
        N = 0
        while node:
            N += 1
            node = node.next
        node = dummy
        for _ in range(N-n-1):
            node = node.next
        node.next = node.next.next
        return dummy.next

The one-pass solution

The key observation is using two pointers to record the location difference. From the final states, if the first pointer points to the tail which is Null, then the second pointer should point to the previous node of the to be deleted node. The distance between the first pointer and the second pointer will be n+1.

How can we maintain this distance?

Put the second point at the head, move the first pointer ahead by (n+1) steps, then the distance between the first pointer and the second pointer will be n+1. After that, move both two pointers together. By doing this, we can make sure that the distance between the first pointer and the second pointer will be exactly n+1. When the first pointer reaches the tail, the first pointer will point to the previous node of ‘to be deleted node’.

Delete it by using prev.next = prev.next.next

The image is from [1]

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(-1)
        dummy.next = head
        first = second = dummy
        for _ in range(n+1):first = first.next
        while first:
            first = first.next
            second = second.next
        second.next = second.next.next
        return dummy.next

Reference

[1]https://leetcode.com/problems/remove-nth-node-from-end-of-list/solution/