Description

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?

Answer & Explaining

#include <stdio.h>
#include <stdlib.h>

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    //head指向頭部，n為倒數第n個要刪掉的節點
    struct ListNode dummy;//虛擬節點dummy node
    dummy.next = head;
    //將*first和*second的位址都指向dummy
    struct ListNode *first = &dummy; 
    struct ListNode *second = &dummy;

    //將first移動n+1步，正好與second距離n
    // Move first pointer n+1 steps ahead
    for (int i = 0; i <= n; i++) {
        first = first->next;
    }
    
    //同時移動兩者
    // Move first to the end, maintaining the gap
    while (first != NULL) { //當first指向Null時停止
        first = first->next;
        second = second->next;
    }
    //first停止時代表second剛好指向要刪除節點的前一個
    // Remove the nth node from the end
    struct ListNode *nodeToDelete = second->next; //刪除second的下個節點
    second->next = second->next->next;//跳過刪除的節點到下個next
    free(nodeToDelete);

    return dummy.next;//回傳第一個位置
}

Testing

#include <stdio.h>
#include <stdlib.h>

// 初始化節點
struct ListNode {
    int val;
    struct ListNode *next;
};


struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    struct ListNode dummy;
    dummy.next = head;
    struct ListNode *first = &dummy;
    struct ListNode *second = &dummy;

    for (int i = 0; i <= n; i++) {
        first = first->next;
    }

    while (first != NULL) {
        first = first->next;
        second = second->next;
    }

    struct ListNode *nodeToDelete = second->next;
    second->next = second->next->next;
    free(nodeToDelete);

    return dummy.next;
}

//創建新節點
struct ListNode* createNode(int val) {
    struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    newNode->val = val;
    newNode->next = NULL;
    return newNode;
}

// 輸出整個List
void printList(struct ListNode* head) {
    struct ListNode* current = head;
    while (current != NULL) {
        printf("%d ", current->val);
        current = current->next;
    }
    printf("\n");
}

// 釋放記憶體空間
void freeList(struct ListNode* head) {
    struct ListNode* tmp;
    while (head != NULL) {
        tmp = head;
        head = head->next;
        free(tmp);//將tmp空間釋放
    }
}

// 測試函數
int main() {
    // 範例一 1->2->3->4->5 ，n=2，變為1->2->3->5
    struct ListNode* head1 = createNode(1);
    head1->next = createNode(2);
    head1->next->next = createNode(3);
    head1->next->next->next = createNode(4);
    head1->next->next->next->next = createNode(5);
    int n1 = 2;

    printf("Original list: ");
    printList(head1);
    head1 = removeNthFromEnd(head1, n1);
    printf("Modified list: ");
    printList(head1);
    freeList(head1);

    // 範例二，1，n =1，變為"空"
    struct ListNode* head2 = createNode(1);
    int n2 = 1;

    printf("Original list: ");
    printList(head2);
    head2 = removeNthFromEnd(head2, n2);
    printf("Modified list: ");
    printList(head2);
    freeList(head2);

    // 範例三，1->2，n=1，變為1
    struct ListNode* head3 = createNode(1);
    head3->next = createNode(2);
    int n3 = 1;

    printf("Original list: ");
    printList(head3);
    head3 = removeNthFromEnd(head3, n3);
    printf("Modified list: ");
    printList(head3);
    freeList(head3);

    return 0;
}