19. Remove Nth Node From End of List

LeetCode

Single Pointer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int max = 0;
        ListNode dummy = new ListNode(0, head);
        ListNode current = dummy;

        while (current != null) {
            max += 1;
            current = current.next;
        }
        int pos_start = max - n - 1;
        current = dummy;
        for (int i = 0; i < pos_start; i++) {
            current = current.next;
        }
        current.next = current.next.next;
        return dummy.next;

    }
}

Remarks:

  1. Use a dummy node to avoid only one node
  2. TC: $O(L)$, L is the length of the list.

Slow and Fast Pointer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode fast = dummy;
        ListNode slow = dummy;

        // Move fast n+1 steps ahead
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }

        // Move both pointers until fast reaches the end
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        // Delete the nth node from end
        slow.next = slow.next.next;

        return dummy.next;
    }
}

Remarks:

  1. Set to pointers: slow and fast, so only go through the list for one time.
  2. TC: $O(L)$