Question

link

   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.

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

Note the special case: if the head node needs to be removed!

Solution

The code explains itself. Just don’t forget the special cases.

My code

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return null;
        }
        ListNode left = head;
        ListNode right = head;
        // important to note that head node can be removed as well!
        // advance right pointer now
        for (int i = 0; i < n; i++) {
            right = right.next;
            if (right == null) {
                right = head;
            }
        }
        // advance left and right pointer together
        while (right.next != null) {
            left = left.next;
            right = right.next;
        }
        // remove the node after left pointer
        // again, the below error check is not necessary
        if (left.next == null) {
            // need to remove the header in this case
            return head.next;
        } else {
            left.next = left.next.next;
            return head;
        }
    }
}