Remove nth node from end of a linked list in C in Linear Time

描述

刪除從串列尾巴往回數第n個節點，n一定有效，回傳輸出串列的head

範例

輸入：1->2->3->4->5, n = 2 輸出：1->2->3->5
輸入：1, n = 1 輸出：NULL
輸入：1->2, n = 2 輸出

想法

用兩個距離n+1的串列指標，一個走訪在前，一個跟在後，走訪在前的指標碰到串列尾節點時，後面的指標在欲刪除節點的前一個。前述的想法適用於3個以上的節點，所以0到2個節點用特殊狀況處理。

實作

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


struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
    int x = 0;
    struct ListNode *rear = NULL;
    struct ListNode *ahead = NULL;

    // Empty linked list
    if (!head)
        return head;
    
    // Linked list with one node, n must be 1
    if (!head->next)
        return NULL;
    
    // Linked list with two nodes, n is either 1 or 2
    if (!head->next->next)
    {
        if (n == 1)
        {
            head->next = NULL;
            return head;
        }

        return head->next;
    }
    
    ahead = head;
    for (x = 0; x < n; x++)
        ahead = ahead->next;   
        
    // head is to be removed
    if (!ahead)
        return head->next;
    
    rear = head;    
    while (ahead->next)
    {
        ahead = ahead->next;
        rear = rear->next;
    }
    
    rear->next = rear->next->next;
    return head;
}