19. Remove Nth Node From End of List (Medium)

Q:

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?

A:
----------------先计算长度----- 再删掉 第 size -n  个 -------------

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // get size
        int size = 0;
        auto cur = head;
        while (cur) {
            cur = cur->next;
            size++;
        }
        ListNode header(0, head);
        ListNode* pre = &header;
        for (int i = 0; i < size - n; i++) {
            pre = pre->next;
        }
        if (pre->next)
            pre->next = pre->next->next;
        return header.next;
    }
};

Mistakes:
1: fastRunner 在跑的时候，光顾忌了其next是否为空，  而没有考虑到， 当我们先设置fastRunner的时候（目的是保持slowRunner和fastRunner的距离为n），有可能已经跑出去了。 ------------solution，设置一个header。 
2: 返回header.next 而不是head， 是考虑到head有可能已经被删除掉了。  sigh~~~~~~~Tiger,  你太SB了

Learned:
-----------------------2nd pass---------- Two runner --------------

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode header(0, head);
        auto slow = &header, fast = &header;// all point to the pre node
        // run n first
        for (int i = 0; i < n; i++) 
            fast = fast->next;
        
        while ( fast->next) {
            slow = slow->next;
            fast = fast->next;
        }
        if (slow->next)
            slow->next = slow->next->next;
        return header.next;
    }
};