[LeetCode] 19. Remove Nth Node From End of List

Posted on | In

Problem

Given a linked list, remove the $n$-th node from the end of list and return its head.

Example:

1
2
3
Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:

Given $n$ will always be valid.

Follow up:

Could you do this in one pass?

Explanation

  1. We can use two pointers to solve this problem.

  2. First, we create a pre and cur pointers that both point to the head. Then, cur pointer move n steps forward. Now, we move both pre and cur pointers at the same speed one step each time, until cur pointer points to the last node. Now, we delete pre.next by setting pre.next = pre.next.next.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null || head.next == null) return null;

        ListNode pre = head, cur = head;
        for (int i = 0; i < n; i++) {
            cur = cur.next;
        }
        if (cur == null) {
            return head.next;
        }

        while (cur.next != null) {
            pre = pre.next;
            cur = cur.next;
        }
        pre.next = pre.next.next;

        return head;
    }
}