Leetcode|24. 两两交换链表中的节点 ● 19.删除链表的倒数第N个节点 ● 面试题 02.07. 链表相交 ● 142.环形链表II
24.
注意:涉及头节点的修改或者删除时,最好设置一个虚拟的头结点,方便简化代码,不必进行是否为头节点的的判断,简化code
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dummyHead = new ListNode(0);//创建一个虚拟的头结点
dummyHead->next = head;//建立联系
ListNode* cur = dummyHead;//简化
while(cur->next!=nullptr&&cur->next->next!=nullptr){//访问的合法性
//记录临时地址的作用是方便找到结点,好进行新的连接
ListNode* tmp = cur->next;//保存临时地址
ListNode* tmp1 = cur->next->next->next;//保存临时地址
cur->next = cur->next->next;//步骤一
cur->next->next = tmp;//步骤二
cur->next->next->next = tmp1;//步骤三
cur = cur->next->next;//移动俩位,准备下一轮交换
}
ListNode* result = dummyHead->next;
delete dummyHead;
return result;
}
};
ListNode* cur = dummyHead;//这一步的操作也是始终知道头节点的位置,方便后续的链表输出
19.
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode* slow = dummyHead;
ListNode* fast = dummyHead;
while(n--&&fast!=nullptr){
fast = fast->next;
}
fast = fast->next;
while(fast!=nullptr){
slow = slow->next;
fast = fast->next;
}
ListNode* tmep = slow->next;
slow->next = slow->next->next;
delete tmep;//记得手动释放内存
return dummyHead->next;
}
};
面试题02.07(链表相交)
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode* curA = headA;
ListNode* curB = headB;
int lenA = 0, lenB = 0;
while (curA != NULL) { // 求链表A的长度
lenA++;
curA = curA->next;
}
while (curB != NULL) { // 求链表B的长度
lenB++;
curB = curB->next;
}
curA = headA;
curB = headB;
// 让curA为最长链表的头,lenA为其长度
if (lenB > lenA) {
swap (lenA, lenB);
swap (curA, curB);
}
// 求长度差
int gap = lenA - lenB;
// 让curA和curB在同一起点上(末尾位置对齐)
while (gap--) {
curA = curA->next;
}
// 遍历curA 和 curB,遇到相同则直接返回
while (curA != NULL) {
if (curA == curB) {
return curA;
}
curA = curA->next;
curB = curB->next;
}
return NULL;
}
};
142
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* fast = head;
ListNode* slow = head;
while(fast!=nullptr&&fast->next!=nullptr){
slow = slow->next;
fast = fast->next->next;
//快慢指针相遇,此时从head和相遇点,同时查找直至相遇
if(slow==fast){
ListNode* index1 = fast;
ListNode* index2 = head;
while(index1!=index2){
index1 = index1->next;
index2 = index2->next;
}
return index1;//返回环的入口
}
}
return nullptr;
}
};
关于fast前进俩步的合法性判断:
为什么可以安全访问 fast->next->next?
链表的结构和指针移动的关系:
在循环中,我们每次让 fast 走两步:fast = fast->next->next。
关键在于:只要我们能保证 fast 和 fast->next 都不为 nullptr,那么 fast->next->next 就一定是一个合法的访问。
fast != nullptr && fast->next != nullptr 的逻辑:
如果 fast != nullptr 且 fast->next != nullptr 成立,意味着:
fast->next 是一个有效的节点(它的指针不为空)。
既然 fast->next 是一个有效节点,它的 next 域(即 fast->next->next)不一定为空,但一定是合法的访问。
如果 fast->next->next 是 nullptr,这只是意味着链表的终点到了,但访问它不会导致程序崩溃。
为什么不需要单独判断 fast->next->next?
我们只需要判断两层的指针(fast 和 fast->next),因为算法的逻辑是:只有在 fast 能再往前移动时才继续循环。
如果 fast->next 是最后一个节点(即 fast->next->next == nullptr),那在本轮循环之后会退出,不会再执行下一次的 fast = fast->next->next。
总结
通过判断 fast != nullptr && fast->next != nullptr,我们确保了每次访问 fast->next->next 都是合法的。
即便 fast->next->next 是 nullptr,也只是说明链表结束了,并不会导致崩溃。下次循环时,会检测到不满足循环条件,程序会安全退出。
所以,这样的判断已经足够确保算法的安全性,不会出现对空指针的非法操作。