Leetcode - 19. Remove Nth Node From End of List

想法策略:

設置兩個 pointer

第一個 pointer 會先走 n+1 步

然後第一個和第二個 pointer 一起前進

所以兩個 pointer 會一直保持 n+1 的距離

直到先出發的 pointer 碰到 NULL 時

後出發的 pointer 所指到的就是要移除的 node

詳細解說:

cur 指到 head，pos_remove 指到 NULL

1. 讓 cur 先走 n 個位置

2. 判斷 cur 是否為空

    1. 如果 cur 不為空，則把 pos_remove 指定為 cur 的位置， cur 在往後走 1 個位置

    (因此目前 pos_remove 和 cur 的距離是 n + 1 個位置)

    2. 如果 cur 是空的，則 cur 和 pos_remove 都不動

3. 直到 cur 碰到尾巴為止， cur 跟 pos_remove 一起往前

4. 如果 pos_remove 為 NULL，就表示要移除的是 head，所以把 head 指定成 head 的下個節點後直接 return head

5. 此時 pos_remove 的下個節點就是要移除的，所以 pos_remove 的下個節點要指向下下個節點(跳過下個節點)

code:

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     struct ListNode *next;

 * };

 */

typedef struct ListNode Node;

Node* removeNthFromEnd(Node* head, int n){

    Node* cur = head;

    Node* pos_remove = NULL;

    //cur increment n steps at first

    for(int index = 0; index < n; index++){

        cur = cur->next;

    }

    //cur and pos_remove increment until cur reaches end

    if(cur){

        pos_remove = head;

        cur = cur->next;

    }

    while(cur){

        pos_remove = pos_remove->next;

        cur = cur->next;

    }

    //remove pos_remove

    if(pos_remove == NULL){

        head = head->next;

        return head;

    }

    if(pos_remove->next){

        pos_remove->next = pos_remove->next->next;

    }

    return head;

}