Leetcode #19 Remove Nth Node from End of List

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Example 1:

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Example 2:

Input: head = [1], n = 1
Output: []

Example 3:

Input: head = [1,2], n = 1
Output: [1]

 

Constraints:

• The number of nodes in the list is sz.
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

 

Follow up: Could you do this in one pass?

There are four things we should know before starting program:

1. Input

2. Output 

3. Data structure

4. How to process the data (tricky one ;-) )

Input

Head and n

•  Head is used to traverse the list
• n is the nth node from the last

Output

Head should be returned.

Data Structure

Use given list data structure

How to process the data?

The tricky part is removing the node at one pass as we don't know the length of the list. 

In the first example, we have the list [1, 2, 3, 4, 5] and n is 2. So 

• 4th node should be removed
• 3rd should point to 5th node

Here, we have odd number(5) of nodes in the list. 

1. Start 🐇 from the head (Eg: 🐇 - 1)
2. Move 🐇 1 step and continue until it reaches 3(n+1 times) from the head. (Eg: 🐇 - 3)
3. Now, Start 🐢 from the head and move 1 step (Eg:  🐢  - 1)
4. When 🐇 reaches last node from n+1th(3) node,  🐢 will be at the node prior to the node to be deleted. (Eg:  🐢 - 3, 🐇 - 5)
5. Now assign the 3rd node's next to 5th node. E

Edge Cases

If we want to delete the head node, we may not know at first. For example, if the list is [1, 2, 3] and n is 3. After rabbit passes the 3rd node only, turtle can start. But the last node is pointing to nullptr. So Turtle can't start. 

• To avoid this, we have a dummy node (with value 0) at the start which would point to head. Have a count to keep track of the nodes passed. 
• Once last node(n+1) is reached, the turtle would start at dummy. 
• Turtle can't move further as the list is empty. So turtle's(dummy) next would point head's next. 

  Node* RemoveNthNodeFromList(int n)
    {
        Node* dummy = CreateNode(0, head);
        Node* rabbit = dummy;
        Node* turtle = dummy;
        int count = 0;
        while (rabbit != nullptr)
        {
            //cout << rabbit->data << " " << count << endl;
            rabbit = rabbit->next;
            if (count > n)
            {
                turtle = turtle->next;
            }
            count++;
        }
        turtle->next = turtle->next->next;
        head = dummy->next;
        return head;
    }