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;
}