Problem

Given a linked list, remove the nth node from the end of list and return its head.

Examples

Example 1:

1
2
3

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
Explanation: Given linked list 1->2->3->4->5 and n = 2, the result is 1->2->3->5.

Example 2:

1
2

Input: head = [1], n = 1
Output: []

Example 3:

1
2

Input: head = [1,2], n = 1
Output: [1]

Solution

Method 1 - Using the Length of the Linked List

  1. Calculate the length of Linked List. Let the length be len.
  2. Print the (len – n + 1)th node from the begining of the Linked List.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

public ListNode removeNthFromEnd(ListNode head, int n) {
    if (head == null)
        return null;

    //get length of list
    ListNode p = head;
    int len = 0;
    while (p != null) {
        len++;
        p = p.next;
    }

    //if remove first node
    int fromStart = len - n + 1;
    if (fromStart == 1)
        return head.next;

    //remove non-first node 
    p = head;
    int i = 0;
    while (p != null) {
        i++;
        if (i == fromStart - 1) {
            p.next = p.next.next;
        }
        p = p.next;
    }

    return head;
}

Method 2 - One Pass - Using Slow and Fast Pointers

Utilize fast and slow pointers, positioning the fast pointer n steps ahead of the slow pointer. When the fast pointer reaches the end, the slow pointer will be at the element just before the target. This method is often referred to as the frame-based solution.

Dry Run

We can first run the code similar to Find Nth Node From End Of Linked List, with some modifications. Firstly, we prepend the list with the dummy node, and slow pointer will point to it.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

public ListNode removeNthFromEnd(ListNode head, int n) {
    if (head == null)
        return null;

	ListNode dummy = new ListNode(0, head);

    ListNode fast = head;
    ListNode slow = dummy;

    for (int i = 0; i < n; i++) {
	    if(fast != null){
		    fast = fast.next;
	    }
    }

    //if remove the first node
    if (fast == null) {
        head = head.next;
        return head;
    }

    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }

    slow.next = slow.next.next;

    return dummy.next;
}

Method 3 : Recursion

Here found is passed by reference and is updated again and again. When we reach the end of the linked list, it is set to 1, otherwise it is incremented by 1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

node * findNthNode(node * head, int find, int& found) {
    if (!head) {
        found = 1;
        return 0;
    }
    node * retval = findNthNode(head -> next, find, found);
    if (found == find)
        retval = head;
    found = found + 1;
    return retval;
}