LeetCode 19. C代码实现

LeetCode 19. 删除链表的第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 ret, *p = &ret, *q = head;//p为慢指针， q为快指针
    ret.next = head;//设置虚拟头节点
    while(n--) q = q->next;//快指针先走
    while(q) q = q->next, p = p->next;//同时走
    q = p->next->next;//q记录p的后继的后继
    free(p->next);//删除p的后继
    p->next = q;//删除完成
    return ret.next;
}