Leetcode 19. Remove Nth Node From End of List

Problem Explanation

The problem is to remove the nth node from the end of a given linked list. The linked list can be any length and the nth node to be removed is counted from the end.

Consider a linked list 1->2->3->4->5 and say we want to remove the 2nd node from the end, which is 4.

Approach

The idea is to leverage two pointers: fast and slow pointers.

Initially, both pointers point to the start of the linked list. First, we advance the fast pointer n nodes ahead. Then we move both the slow and fast pointers one node a time. When the fast pointer reaches the end of the linked list, the slow pointer will be at the (n+1)th node from the end.

Now, since we want to remove nth node from the end, the node to remove will be the one after the slow pointer. So we direct the slow pointer's next pointer to point to the next node's next node (skipping over the node to be removed), thus effectively removing the nth node from the end of the linked list.

Solution

Python

1
2python
3class Solution:
4    def removeNthFromEnd(self, head, n):
5        slow = fast = head
6        for _ in range(n):
7            fast = fast.next
8        if not fast:
9            return head.next
10        while fast.next:
11            slow = slow.next
12            fast = fast.next
13        slow.next = slow.next.next
14        return head

Java

1
2java
3public class Solution {
4    public ListNode removeNthFromEnd(ListNode head, int n) {
5        ListNode slow = head, fast = head;
6        for(int i=1; i<=n; i++){
7            fast = fast.next;
8            if(fast == null)
9                return head.next;
10        }
11        while(fast.next != null){
12            slow = slow.next;
13            fast = fast.next;
14        }
15        slow.next = slow.next.next;
16
17        return head;
18    }
19}

Javascript

1
2javascript
3class Solution {
4  removeNthFromEnd(head, n) {
5    let slow = head, fast = head;
6    for(let i=0; i<n; i++){
7      fast = fast.next;
8      if(fast == null)
9        return head.next;
10    }
11    while(fast.next != null){
12      slow = slow.next;
13      fast = fast.next;
14    }
15    slow.next = slow.next.next;
16
17    return head;
18  }
19}

C++

1
2c++
3class Solution {
4public:
5    ListNode* removeNthFromEnd(ListNode* head, int n) {
6       ListNode* slow = head;
7       ListNode* fast = head;
8
9       while (n--)
10         fast = fast->next;
11
12       if (fast == nullptr)
13         return head->next;
14
15       while (fast->next) {
16         slow = slow->next;
17         fast = fast->next;
18       }
19       slow->next = slow->next->next;
20
21       return head;
22    }
23};

C#

1
2csharp
3public class Solution {
4    public ListNode RemoveNthFromEnd(ListNode head, int n) {
5        ListNode slow = head, fast = head;
6        for(int i=0; i<n; i++){
7            fast = fast.next;
8            if(fast == null)
9                return head.next;
10        }
11        while(fast.next != null){
12            slow = slow.next;
13            fast = fast.next;
14        }
15        slow.next = slow.next.next;
16
17        return head;
18    }
19}

The time complexity of the above solution is O(L), where L is the length of the linked list. The space complexity is O(1), as we are only using two pointers.### Ruby

1
2ruby
3class Solution
4    def remove_nth_from_end(head, n)
5        slow = fast = head
6        n.times {
7            fast = fast.next
8            return head.next unless fast
9        }
10        while fast.next
11            slow = slow.next
12            fast = fast.next
13        end
14        slow.next = slow.next.next
15
16        head
17    end
18end

Swift

1
2swift
3class Solution {
4    func removeNthFromEnd(_ head: ListNode?, _ nthNode: Int) -> ListNode? {
5        let dummy: ListNode? = ListNode(0)
6        dummy?.next = head
7        var first: ListNode? = dummy
8        var second: ListNode? = dummy
9
10        for i in 1...nthNode+1 {
11            first = first?.next 
12        }
13
14        while first != nil {
15            first = first?.next
16            second = second?.next
17        }
18        
19        second?.next = second?.next?.next
20
21        return dummy?.next
22    }
23}

PHP

1
2php
3class Solution
4{
5  function removeNthFromEnd($head, $n) {
6    $slow = $fast = $head;
7    for($i = 0; $i < $n; $i++){
8      $fast = $fast->next;
9      if($fast === null)
10        return $head->next;
11    }
12    while($fast->next !== null){
13      $slow = $slow->next;
14      $fast = $fast->next;
15    }
16    $slow->next = $slow->next->next;
17
18    return $head;
19  }
20}

Each solution uses the same logic: two pointers, fast and slow, are employed. The fast pointer advances n steps first, then both pointers take steps together until the fast pointer reaches null. At this point, the slow pointer is at the previous node of the nth node from the end, and we can delete the nth node by adjusting the slow node's next pointer. This allows us to traverse the linked list only once, resulting in a time complexity of O(L), where L is the length of the linked list and space complexity is O(1).