## 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.

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
``````

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 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]

``````

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 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