Advertisement
imashutosh51

Nth node from end of linked list

Aug 10th, 2022 (edited)
279
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.08 KB | None | 0 0
  1. /*
  2. Method 1:find length then do len-n and print (len-n)th node
  3.          T.C O(n) but two pass S.C O(1)
  4. Mthod 2:use recursion T.C O(n), S.C O(n) due to stack of recursion calls
  5. Method 3: use two pointers
  6.     first make two pointer.keep first pointer at head and
  7.     move second pointer to nth node.Now first pointer is
  8.     nth left of second pointer.now move both pointer one
  9.     step at a time until second reaches at end.
  10.     still first pointer will be nth left of second pointer
  11.     and end of linkedlist also.
  12.     T.C O(n) two pass but one pass is not full linked list,S.C O(1)
  13. */
  14.         fast = head
  15.         slow = head
  16.  
  17.         # Move fast n steps ahead
  18.         for _ in range(n):
  19.             fast = fast.next
  20.  
  21.         # If fast is None, that means we need to remove the head
  22.         if not fast:
  23.             return head.next
  24.  
  25.         # Move both pointers until fast reaches the last node
  26.         while fast.next:
  27.             slow = slow.next
  28.             fast = fast.next
  29.  
  30.         # Remove the target node
  31.         slow.next = slow.next.next
  32.  
  33.         return head
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement