Given a linked list, remove the n-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?

Difficulty: interview

Starter code:

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
    self.val = val
    self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        

Solutions:
# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     # @return a ListNode
     def removeNthFromEnd(self, head, n):
         dummy=ListNode(0); dummy.next=head
         p1=p2=dummy
         for i in range(n): p1=p1.next
         while p1.next:
             p1=p1.next; p2=p2.next
         p2.next=p2.next.next
         return dummy.next
             
             
         

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def removeNthFromEnd(self, head, n):
         """
         :type head: ListNode
         :type n: int
         :rtype: ListNode
         """
         left = head
         right = head
         for _ in range(n):
             right = right.next
         if not right:
             return head.next
         
         while right.next:
             left = left.next
             right = right.next
         
         left.next = left.next.next
         return head
             

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def removeNthFromEnd(self, head, n):
         dummy = ListNode(0)
         dummy.next = head
         fast = slow = dummy
         for _ in range(n):
             fast = fast.next
         while fast and fast.next:
             fast = fast.next
             slow = slow.next
         slow.next = slow.next.next
         return dummy.next

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def removeNthFromEnd(self, head, n):
         """
         :type head: ListNode
         :type n: int
         :rtype: ListNode
         """
         dummy = ListNode(0)
         dummy.next = head
         slow = fast = dummy
 
         for _ in range(n):
             fast = fast.next
 
         while fast.next != None:
             fast = fast.next
             slow = slow.next
 
         slow.next = slow.next.next
         temp = dummy.next
         while temp != None:
             print(temp.val)
             temp = temp.next
         return dummy.next

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def removeNthFromEnd(self, head, n):
         """
         :type head: ListNode
         :type n: int
         :rtype: ListNode
         """
         
         ''' first trial. O(L) time, O(L) space complexity. 
         nodes_list = []
         cursor = head
         while cursor != None:
             nodes_list.append(cursor)
             cursor = cursor.next
         
         if n == len(nodes_list):
             head = head.next
         else :
             nodes_list[-n-1].next = nodes_list[-n].next
         
         return head
         '''
         
         # second trial after getting a hint from its solution.
         dummy = ListNode(0)
         dummy.next = head
         target_prev = dummy
         tail = head
         dist = 0
         while tail != None:
             if dist < n:
                 tail = tail.next
                 dist += 1
             else :
                 target_prev = target_prev.next
                 dist -= 1
         
         target_prev.next = target_prev.next.next
         return dummy.next

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def removeNthFromEnd(self, head, n):
         positions = {}
         cur = head
         i = 0
         while cur:
             i += 1
             positions[i] = cur
             cur = cur.next
         
         if i == 1:
             return None
         elif n == i:
             return head.next
         else:
             parent = positions[i - n]
             toRemove = parent.next
             parent.next = toRemove.next
         
         return head
         

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def removeNthFromEnd(self, head, n):
         temp = head
         counter = 0
         while(temp!=None):
             counter += 1
             temp = temp.next
         timeToVisit = counter - n
         if timeToVisit == 0:
             return head.next
         if timeToVisit == 1:
             head.next = head.next.next
             return head
         nodeToDel = head
         while(timeToVisit>0):
             nodeToDel = nodeToDel.next
             timeToVisit -= 1
             if timeToVisit == 1:
                 nodeToSave = nodeToDel
                 nodeToNext = nodeToDel.next.next
                 nodeToSave.next = nodeToNext
         return head
         """
         :type head: ListNode
         :type n: int
         :rtype: ListNode
         """
         

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     
     # one pass O(N) deletion approach using 2 ptr
     def removeNthFromEnd(self, head, n):
         """
         :type head: ListNode
         :type n: int
         :rtype: ListNode
         """
 
         # will point at node to be deleted
         slow = head
 
         # assists in finding the nth node from end
         fast = head
 
         # node before node to be deleted
         prev = None
 
         for i in range(n):
 
             fast = fast.next
 
         # want to delete head
         if fast == None:
 
             slow = head
             head = head.next
             slow.next = None
 
         # want to delete a node besides head
         else:
 
             while fast:
 
                 prev = slow
                 slow = slow.next
                 fast = fast.next
 
             prev.next = slow.next
             slow.next = None
 
         return head


# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def removeNthFromEnd(self, head, n):
         """
         :type head: ListNode
         :type n: int
         :rtype: ListNode
         """
         fast = slow = head
         for _ in range(n):
             fast = fast.next
         if not fast:
             return head.next
         while fast.next:
             fast = fast.next
             slow = slow.next
         slow.next = slow.next.next
         return head
         

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def removeNthFromEnd(self, head, n):
         """
         :type head: ListNode
         :type n: int
         :rtype: ListNode
         """
         current = head
         while current is not None:
             i = n
             runner = current.next
             while i > 1:
                 if runner is not None:
                     runner = runner.next
                     i -= 1
             if runner is None:
                 return head.next
             elif runner.next is None:
                 current.next = current.next.next
                 return head
             
             current = current.next
         return head

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 #[]
 #[1]
 class Solution:
     def removeNthFromEnd(self, head, n):
         """
         :type head: ListNode
         :type n: int
         :rtype: ListNode
         """
         if not head.next:
             return []
 
         dummy=ListNode(None)
         pre=ListNode(None)
         dummy.next=head
         pre.next=head
         count=1
         while head.next:
             if count<n:
                 count+=1
                 head=head.next
             else:
                 pre=pre.next
                 count-=1 
         if pre.val==None:
             return dummy.next.next
         else:
             pre.next=pre.next.next
             return dummy.next
                 
             
         

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def removeNthFromEnd(self, head, n):
         """
         :type head: ListNode
         :type n: int
         :rtype: ListNode
         """
         i=0
         node=head
         while(node):
             i=i+1
             if(node.next):
                 node=node.next
             else:
                 break
         num=i-n
         if(num==0):
             return head.next
         
         cur=head
         for k in range(num-1):
             cur=cur.next
         cur.next=cur.next.next
         return head

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def removeNthFromEnd(self, head, n):
         """
         :type head: ListNode
         :type n: int
         :rtype: ListNode
         """
         if head is None:
             return None
         fast = head
         slow = head
         for i in range(0, n):
             slow = slow.next
         if slow is None:
             return head.next
         while slow.next is not None:
             slow = slow.next
             fast = fast.next
         fast.next = fast.next.next
         
         return head