Remove Nth Node From End of List

1. Problem Description

Given a linked list, remove the nth node from the end and return the head of the list. For example, given the linked list: 1->2->3->4->5, n = 2. after removing the nth node from the end, the list becomes 1->2->3->5.

2. Approach

1. Approach 1
   • Traverse once to count the nodes, then on the second pass move to the count-n node
2. Approach 2
   • Two pointers
   • Move one pointer n steps ahead first
   • Move both pointers together until the fast pointer reaches the end

3. Implementation

3.1. Two Passes

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    h := head
    count := 0
    for h != nil {
        count++
        h = h.Next
    }

    dummyHead := &ListNode{
        Next:head,
    }
    h = dummyHead
    for i := 0; i < count-n; i++{
        h  = h.Next
    }
    delNode := h.Next
    h.Next = delNode.Next
    delNode.Next = nil
    return dummyHead.Next
}

3.2. Two Pointers

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {

    dummyHead := &ListNode{Next:head}
    fast := dummyHead
    for i:= 0; i < n; i++ {
        fast = fast.Next
    }
    slow := dummyHead
    for fast != nil && fast.Next != nil {
        fast = fast.Next
        slow = slow.Next
    }
    slow.Next = slow.Next.Next
    return dummyHead.Next

}

4. References

• Remove the Nth Node from the End of a Linked List - NowCoder
• 19. Remove Nth Node From End of List - LeetCode