[Coderust] Remove Nth Node From End of List

 

 

Problem

 

 

 

 

---

 

Solution

 

Need to find a way to both reach the end of the list with one pointer (so that we can find the n'th node from the end) and also the n'th node from the end simultaneously with a second pointer.

 

Fast pointer will have a head start by n nodes. This will cause slow pointer to reach the n'th node from the end at the same time that fast pointer reaches the end.

 

Actually, slow pointer need access to the node before the target node, so use fast.next == null as the exit condition instead of fast==null to stop one node earlier.

 

To handle the edge case where n is the same as the length of the list (target node is the head), just return head.next.

 

 

 

# 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: Optional[ListNode], n: int) -> Optional[ListNode]:
        fast = slow = head
        
        for _ in range(n):
            fast = fast.next
        
        # if n is equal to the len of list, fast should have gone beyond the end of list
        # so remove the head
        if not fast:
            return head.next
        
        while fast.next:
            slow = slow.next
            fast = fast.next
        
        slow.next = slow.next.next
        return head

 

 

https://leetcode.com/problems/remove-nth-node-from-end-of-list/discuss/1164542/JS-Python-Java-C%2B%2B-or-Easy-Two-Pointer-Solution-w-Explanation

JS, Python, Java, C++ | Easy Two-Pointer Solution w/ Explanation - LeetCode Discuss

 

Time Complexity

O(N)

 

 

Space Complexity

O(1)