Given a linked list:
class ListNode(object): def __init__(self, x): self.val = x self.next = None
remove the node from the end of list and return its head.
Note: will always be valid.
For this we will use a two pointer technique. That is, we will iterate over our list using two pointer and . First, we will fast-forward positions. That is, will be nodes ahead of .
We will then iterate over the list using and by pointing them to the next nodes one-by-one. When reaches the end of the list, we will know that will point to the node from the end of list. We will then adjust the next pointers accordingly and return the head of the list.
# Definition for singly-linked list. class ListNode(object): def __init__(self, x): self.val = x self.next = None def __str__(self): head = self ans = '' while head != None: ans = ans + str(head.val) head = head.next if head != None: ans = ans + '->' return ans class Solution(object): def removeNthFromEnd(self, head, n): """ :type head: ListNode :type n: int :rtype: ListNode """ i = head j = head # Fast forward j n positions for count in range(0,n): j = j.next # Iterate over the list one by one until j hits the end while j != None and j.next != None: j = j.next i = i.next # j reached the end. This means i points to the (n+1)th node from the end of list (since j was n nodes ahead) if j != None: i.next = i.next.next else: # Remove i itself head = head.next return head def main(): head = ListNode(1) node = head for x in range(2, 6): node.next = ListNode(x) node = node.next solution = Solution() print(solution.removeNthFromEnd(head, 2)) head = ListNode(1) print(solution.removeNthFromEnd(head, 1)) head = ListNode(1) head.next = ListNode(2) print(solution.removeNthFromEnd(head, 2)) if __name__ == "__main__": main()