LeetCode | 19. 删除链表的倒数第 N 个结点

LeetCode | 19. 删除链表的倒数第 N 个结点

OJ链接

思路：

• 定义虚拟头节点dummy并初始化使其指向head
• 然后定义快慢指针
• 让快指针先走n步
• 然后一起走
• 最后删除倒数第n个节点
• 然后释放虚拟节点dummy

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    //定义虚拟头节点dummy 并初始化使其指向head
    struct ListNode* dummy = malloc(sizeof(struct ListNode));
    dummy->val = 0;
    dummy->next = head;
    //定义 fast slow 双指针
    struct ListNode* fast = head;
    struct ListNode* slow = dummy;

    for (int i = 0; i < n; ++i) {
        fast = fast->next;
    }
    while (fast) {
        fast = fast->next;
        slow = slow->next;
    }
    slow->next = slow->next->next;//删除倒数第n个节点
    head = dummy->next;
    free(dummy);//删除虚拟节点dummy
    return head;
}