19. Remove Nth Node From End of List
1. Description
Given the head of a linked list, remove the nth node from the end of the list and return its head.
2. Follow Up
Could you do this in one pass?
3. Example
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]
4. Constraints
- The number of nodes in the list is sz.
- 1 <= sz <= 30
- 0 <= Node.val <= 100
- 1 <= n <= sz
5. Solutions
My Accepted Solution(Follow Up)
n is the number of nodes in m_head
Time complexity: O(n)
Space complexity: O(1)
class Solution
{
public:
// ListNode* removeNthFromEnd(ListNode* head, int n)
ListNode* removeNthFromEnd(ListNode *m_head, int number)
{
auto fastNode = m_head;
for( ; number > 0; number--) fastNode = fastNode->next;
// that means number is equal to the number of nodes in m_head
// so we should delete the first node in m_head
if(!fastNode) return m_head->next;
auto slowNode = m_head;
for(; fastNode->next; slowNode = slowNode->next, fastNode = fastNode->next) ;
slowNode->next = slowNode->next->next;
return m_head;
}
};