19. Remove Nth Node From End of List

1.問題

• 給予一個list, 刪除倒數第n個node

2.想法

• 1.用traversal計算list有多長

• 2.刪除node

  • 需要兩個node: current, previous,分別指向目標及目標的前一個node

  • 將current移動到目標

  • 刪除node

3.程式碼

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *current = head;
        ListNode *previous = 0;
        if (!head->next && n == 1) {
            return NULL;
        }
        //Count the list
        int cnt = 0;
        while(current) {
            cnt++;
            current = current->next;
        }
        
        //Find the target
        current = head;
        int index = 0;
        while(current && cnt - n != index) {
            index++;
            previous = current;
            current = current->next;
        }
        
        //Delete node
        if (!previous) {
            //If the target is the head
            head = current->next;
        } else {
            //If the target is not the head
            previous->next = current->next;
        }
        
        current = 0;
        return head;
    }
};

4.Performance