提示：以下是本篇文章正文内容，下面案例可供参考
一、哑结点
在leetcode平台中, 单链表的头结点同时也作为链表的第一个结点使用
也就是说, 相对于王道数据结构书上和 前面几篇博客 的单链表表示方法中, 使用一个无数据域的结点作为虚拟头结点(head结点)的这种方式, 在做力扣单链表题时, 会使用到添加哑结点dummy的技巧. 这也就是前文说的虚拟头结点的技巧;
一句话就是, 在leetcode题解中在链表第一个结点钱添加dummy哑结点就等同于构造了一个带有虚拟头结点的单链表
二、快慢指针
在leetcode-19题中, 使用到了快慢指针的技巧, 这道题的要求是删除倒数第N个结点
下面是题解
/**
* 快慢指针
* 快指针先走n个位置,与慢指针拉开n
* 然后快慢指针同时再向后移动,
* 直到快指针走到表尾了,删除掉慢指针指向的元素
* */
ListNode* removeNthFromEnd(ListNode* head, int n) {
// dummy指向第一个结点
// dummy 哑结点,在链表头结点前再接上去的一个结点
ListNode* dummy = new ListNode(0, head);
ListNode* first = head; // 快指针指向第一个结点
ListNode* second = dummy; // 慢指针指向哑结点
for (int i = 0; i < n; ++i) { // 快指针先出发n位
first = first->next;
}
while (first) {
first = first->next;
second = second->next;
}
second->next = second->next->next; // 删除倒数第n个位置的元素
ListNode* ans = dummy->next; // dummy->next指向了第一个结点
delete dummy;
return ans;
}
当使用快慢指针时, 由于添加了哑结点, 因此慢指针自然而然地指向了哑结点(也就是链表第一个结点的前一个位置), 这样快慢指针就自然地区分开了. 而且当链表的结点只有一个时, 也不用判断快慢指针是否指在同一个结点上;
对于这道题, 使用快慢指针, 让fast指针先出发n位, 与slow拉开n位的差距, 这样当fast指空时, slow刚好位于需要删除的结点的前一个位置,这样接下来只要执行删除操作即可;
三、交换/删除结点
在单链表中, 交换和删除结点都是常考的操作
- 删除结点
// 删除fast指向的结点
p->next = p->next->next;
或
// q指向被删除结点
q = p->next;
p->next = q->next; // 将q指向的结点从链表中断开
- 交换结点
p->next = node_2; // 1
node_1->next = node_2->next; // 2
node_2->next = node_1; // 3
在第2步中, node1必须先和node2的后继连接上,防止后继丢失
未完待续… …