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

題目為給定一個鏈結串列 ( Linked List ) 與一個數字 n ，n 代表要移除從後面數來第幾個節點。

原文題目如下

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?

解題策略為透過三個指標，第一個為遍歷整個鏈結串列 ( Link List ) 用的，第二個指標為與第一個指標差 n ，用以指出倒數第 n 個節點，第三個指標為第二個指標後面一個，用以移除第 n 個節點用。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
    struct ListNode* first = head;
    struct ListNode* second = head;
    struct ListNode* secondback = head;
    for(int i = 0;i<n;i++){
        first = first->next;
    }
    while(first!=NULL){
        if(second == secondback){
        }
        else{
            secondback = secondback->next;
        }
        first = first->next;
        second = second->next;
    }
    if(second == head)
        head = second->next;
    else
        secondback->next = second->next;
    
    return head;
}

下面是時間與空間之消耗

Runtime: 0 ms, faster than 100% of C online submissions for Remove Nth Node From End of List.

Memory Usage: 5.8 MB, less than 81.55% of C online submissions for Remove Nth Node From End of List.

下一題連結 : LeetCode 20. Valid Parentheses ( C ) – Easy