Remove Nth Node From End of List

Problem: Remove Nth Node from End of List

Easy way to solve this problem is go through the list to find the demanded node and delete it. We can maintain an array of nodes so that we can fetch the node easily by index.

However, there's a cooler way to do this by sliding window. The general idea is to set a sliding window of size n and slide it from the head of list to the tail. When the window's tail gets the list's tail, the head of the window is what we want to delete.

Code in Python:

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        prev, wHead, wTail = None, head, head
        for i in xrange(n-1):
            wTail = wTail.next
        if not wTail.next:
            return head.next
        while wTail.next:
            prev, wHead, wTail = wHead, wHead.next, wTail.next
        prev.next = wHead.next
        return head
        # nodes = []
        # pointer = head
        # while pointer:
        #     nodes.append(pointer)
        #     pointer = pointer.next

        # i = len(nodes)-n
        # if i == 0:
        #     return head.next
        # if nodes[i-1]:
        #     nodes[i-1].next = nodes[i].next

        # return head

Details:

• Note that to delete a node in a list, we need to get its previous node. In this solution we maintain a reference named "prev" to do that.
• Again, use pointers to implement sliding window, not a real window.

Code in Java:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) return null;

        ListNode tail = head;
        for (int i = 0; i < n; i++) {
            tail = tail.next;
        }

        if (tail == null) return head.next;

        ListNode target = head;
        while (tail.next != null) {
            target = target.next;
            tail = tail.next;
        }
        target.next = target.next.next;

        return head;
    }
}