24. 两两交换链表中的节点
题目链接：24. 两两交换链表中的节点
文档讲解：代码随想录
状态：递归和双指针AC，学习了虚拟头节点的用法
思路
双指针：我的思路，直接处理头节点，灵感来源于链表反转，但是对于本题来说，难点在于下图中步骤三的处理，节点3与4还没有互换位置，需要节点1直接指向节点4，较为繁琐。
虚拟头节点：每次处理cur节点后面的两个节点加当前cur节点的指针，重点在于步骤三，仅指向下个节点即可，重点理解！！！
递归法：三板斧搞清楚很简单了。
题解
class Solution {
public:
ListNode* swapPairs(ListNode* head)
{//用模拟写出（双指针）
// if(head == nullptr || head->next == nullptr)return head;
// else
// {
// ListNode *result = head->next;
// while(head!=nullptr && head->next!=nullptr)
// {
// ListNode *tail = head->next;
// ListNode *temp = tail->next;
// tail->next = head;
// if(temp == nullptr)head->next = nullptr;
// else if(temp->next == nullptr)head->next = temp;
// else head->next = temp->next;
// //head->next = temp==nullptr?nullptr:temp->next;
// head = temp;
// }
// return result;
// }
//使用虚拟头节点,更符合逻辑！！
ListNode *dummy_head = new ListNode(0,head);
ListNode *cur = dummy_head;
while(cur->next!=nullptr && cur->next->next!=nullptr)
{
ListNode *temp = cur->next;
cur->next = temp->next;
ListNode *temp2 = cur->next->next;
cur->next->next = temp;
temp->next = temp2;
cur = temp;
}
return dummy_head->next;
//递归掌握了思想轻松写出
// if(head == nullptr||head->next == nullptr)return head;
// ListNode *newhead = swapPairs(head->next->next);
// ListNode *result = head->next;
// head->next->next = head;
// head->next = newhead;
// return result;
}
};
19.删除链表的倒数第N个节点
题目链接：19.删除链表的倒数第N个节点
文档讲解：代码随想录
状态：瞥了一下思路，AC，掌握一种处理倒数的思想
思路
对于顺序结构这类，正序很简单，反而倒数的很难受，如何破解？
重点思路：两个指针岔开并行，一个到末尾，另一个即是倒数所求。
题解
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode *dummy_head = new ListNode(0,head);
ListNode *fast = dummy_head;
ListNode *slow = dummy_head;
while(n--)fast = fast->next;
while(fast->next != nullptr)
{
fast = fast->next;
slow = slow->next;
}
ListNode *temp = slow->next;
slow->next = slow->next->next;
delete temp;
return dummy_head->next;
}
};
面试题 02.07. 链表相交
题目链接：面试题 02.07. 链表相交
文档讲解：代码随想录
状态：撇了眼思路AC，是模拟题，想思路
思路
此题关键点在于链表相交后续均为一体
如何思考？链表，还是单向的，那只能从前往后遍历了；但是明显长度不同遍历没用啊，如何解决？找到起始遍历点最重要，从后往前捋，以短为头。
题解
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int lenA = 0,lenB = 0;
ListNode *curA = headA;
ListNode *curB = headB;
while(curA!=nullptr)
{
lenA++;
curA = curA->next;
}
while(curB!=nullptr)
{
lenB++;
curB = curB->next;
}
curA = headA;
curB = headB;
if(lenA<lenB)
{
swap(lenA,lenB);
swap(curA,curB);
}
int n = lenA-lenB;
while(n--)curA = curA->next;
while(curA!=nullptr)
{
if(curA == curB)return curA;
curA = curA->next;
curB = curB->next;
}
return nullptr;
}
};
142.环形链表II
题目链接：142.环形链表II
文档讲解：代码随想录
状态：哈希表简单AC，数学解法理解解决，很厉害
思路
set真的好用，利用环形链表重复的特性
数学解法，感觉很难想到，但是并不难理解。根据下面图解，主要理解：追及相遇设置fast、slow两个节点、若有环slow一定是第一圈内被遇到、若有环fast一定走过一圈环才可能遇到slow、我们用程序处理fast与slow可以得到什么（得到相遇点指针）？
题解
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
// set<ListNode *> uset;
// ListNode *cur = head;
// while(cur!=nullptr)
// {
// if(uset.find(cur)!=uset.end())return cur;
// uset.insert(cur);
// cur = cur->next;
// }
// return nullptr;
ListNode *fast = head;
ListNode *slow = head;
while(fast!=nullptr && fast->next!=nullptr)
{
slow = slow->next;
fast = fast->next->next;
if(slow == fast)
{
slow = head;
while(slow!=fast)
{
slow = slow->next;
fast = fast->next;
}
return fast;
}
}
return nullptr;
}
};
链表总结
玩了两天链表，渐渐感觉难点在于（与数组的不同）指针的处理，即数据结构的理解。最简单的增、删、改，扩展的反转、交换，以及虚拟头节点的使用时机。对于复杂的环形链表与双链表，要注意一些模拟类型的题目的固定解决方式。