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.
- Start 🐇 from the head (Eg: 🐇 - 1)
- Move 🐇 1 step and continue until it reaches 3(n+1 times) from the head. (Eg: 🐇 - 3)
- Now, Start 🐢 from the head and move 1 step (Eg: 🐢 - 1)
- When 🐇 reaches last node from n+1th(3) node, 🐢 will be at the node prior to the node to be deleted. (Eg: 🐢 - 3, 🐇 - 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;}
Comments
Post a Comment