Description

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

Example 1:

1Input: head = [1,2,3,4,5], n = 2
2Output: [1,2,3,5]

Example 2:

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

Example 3:

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

Constraints:

  • The number of nodes in the list is sz.
  • 1 <= sz <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz

Follow up: Could you do this in one pass?

Solution

Using ArrayList

One potential solution is to find the length of the list in the first pass. Now, to remove nth node from the end is equal to removing size - nth node from the start. For example, if list is [1, 2, 3, 4, 5] and n=2 then size=5 and we want to remove 5-2=3 node with start index as zero. In order to do this, we first find the length of the list by iterating over the list. Next time when we start iteration from the start of the list, we have to reach upto 3rd node which is previous to the node we want to delete. This is because we will need the previous node in singly linked list in order to delete the next node.

 1class Solution {
 2    public ListNode removeNthFromEnd(ListNode head, int n) {
 3        if (head == null) {
 4            return null;
 5        }
 6        // Find length of the list
 7        ListNode current = head;
 8        int length = 0;
 9        while (current != null) {
10            length++;
11            current = current.next;
12        }
13        // Iterate upto n-1 from previous
14        // handle edge cases like when previous is -1
15        int i = 0;
16        current = head;
17        while ((length - n) > 0 && (i != length - n - 1)) {
18            current = current.next;
19            i++;
20        }
21        if (length - n == 0) {
22            head = head.next;
23        } else {
24            current.next = current.next.next;
25        }
26        return head;
27    }
28}

Using Two pointers

In this problem, basically we want to find the previous node of the nth node from the end. If we start the fast pointer at n+1 node from head and slow pointer at head and in each iteration move both pointers forward by one position. When fast pointer reaches end of the list, the slow pointer will be at n-1 from the end. Now, we simply need to remove the slow.next node from the list and return the head.

 1class Solution {
 2    public ListNode removeNthFromEnd (ListNode head, int n) {
 3        if (head == null) {
 4            return null;
 5        }
 6        ListNode dummy = new ListNode(0, head);
 7        ListNode ahead = dummy;
 8        ListNode behind = dummy;
 9        for (int i = 0; i <= n; i++) {
10            ahead = ahead.next;
11        }
12        while (ahead != null) {
13            ahead = ahead.next;
14            behind = behind.next;
15        }
16        behind.next = behind.next.next;
17        return dummy.next;
18    }
19}
  • Time Complexity: O(n)
  • Space Complexity: O(1)