19. Remove Nth Node From End of List

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

Example:

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?

Thoughts:

1. dfs "backtracking": recursively determine the index, with Value-Shifting

2. Index and Remove: recursively determine the index, with "deleting" the nth node (selecting the next node)

3. Two pointer: Having fast node go n steps first then when fast reaches the end (fast.next == null); slow.next is the node to be deleted: (if after n step fast is null (means n == len(list)) then only move the head by returning head.next; else slow and fast go until fast reaches the end, and assign slow.next = slow.next.next

from: StefanPochmann's post

Code: Value-Shifting

class Solution:
    def removeNthFromEnd(self, head, n):
        def index(node):
            if not node:
                return 0
            i = index(node.next) + 1
            if i > n:
                node.next.val = node.val
            return i
        index(head)
        return head.next

Code: Index and Remove

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        def backRemove(node):
            if not node: return 0, node

            i, node.next = backRemove(node.next)

            return i + 1, (node, node.next)[i + 1==n]

        return backRemove(head)[1]

Code: two pointer: slow.next is the node to be deleted

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        slow = fast = head
        # Given n is valid
        for _ in range(n):
            fast = fast.next

        if not fast: return head.next # remove head

        while fast.next:
            fast = fast.next
            slow = slow.next

        slow.next = slow.next.next

        return head