24. 两两交换链表中的节点
mydemo（超时）
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dummy = new ListNode();
dummy->next = head;
ListNode* cur = dummy;
ListNode* tmp1 = cur->next;
ListNode* tmp2;
ListNode* tmp3;
if(tmp1 != NULL)
{
tmp2 = tmp1->next;
if(tmp2 != NULL)
tmp3 = tmp2->next;
else
tmp3 = NULL;
}
else
{
tmp2 = NULL;
tmp3 = NULL;
}
while(cur->next != NULL || cur->next->next != NULL)
{
tmp2->next = tmp1;
tmp1->next = tmp3;
cur->next = tmp2;
cur = tmp2;
}
return dummy->next;
}
};
mydemo2
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dummy = new ListNode();
dummy->next = head;
ListNode* cur = dummy;
ListNode* tmp;
while(cur->next != NULL || cur->next->next != NULL)
{
tmp = cur->next;
cur->next = cur->next->next;
tmp->next = cur->next->next;
cur->next->next = tmp;
cur = cur->next;
}
return dummy->next;
}
};
报错，tmp->next = cur->next->next;这一行报了空指针错误
Line 25: Char 36: runtime error: member access within null pointer of type 'ListNode' (solution.cpp)
两个错误
//while(cur->next != NULL || cur->next->next != NULL)
while(cur->next != NULL && cur->next->next != NULL)
tmp = cur->next;
cur->next = cur->next->next;
tmp->next = cur->next->next;
cur->next->next = tmp;
//cur = cur->next;
cur = cur->next->next;
关于指针的一点思考
指向 = 地址
ListNode* curl = new ListNode(0);
ListNode* head = new ListNode(1);
curl->next = head;
此时,curl->相当于指向，head相当于地址
直观来看，就是改变箭头指向的终点
19. 删除链表的倒数第N个结点
mydemo 暴力法
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode();
dummy->next = head;
ListNode* cur = dummy;
int len = 0;
int i = 0;
while(cur->next)
{
cur = cur->next;
len++;
}
cur = dummy;
while(i<len-n)
{
cur = cur->next;
i++;
}
ListNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
return dummy->next;
}
};
双指针法
思路：要删倒数第N个元素，那就先让快指针走N步，再让快慢指针一起动，当快指针到达末尾时，满指针也就到达了要删除的地方
细节：为了删除节点，慢指针应当到达要删除节点的前一个节点处，所以快指针应当先走N+1步
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode();
dummy->next = head;
ListNode* fast = dummy;
ListNode* slow = dummy;
n++;
while(n-- && fast!=NULL) //fast!=NULL 防止空指针错误
{
fast = fast->next;
}
while(fast)
{
slow = slow->next;
fast = fast->next;
}
if(slow->next!=NULL) //防止空指针错误
{
ListNode* tmp = slow->next;
slow->next = slow->next->next;
delete tmp;
}
return dummy->next;
}
};
面试题 02.07. 链表相交
mydemo 暴力遍历法——成功
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode* fast = headA;
ListNode* slow;
while(fast)
{
slow = headB; //每次遍历之前，先回到起点
while(slow)
{
if(fast == slow)
{
return fast;
}
slow = slow->next;
}
fast = fast->next;
}
return NULL;
}
};
注意，在每次遍历前需要先回到起点
slow = headB; //每次遍历之前，先回到起点
相减法——（代码随想录）
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if(headA==NULL || headB==NULL) return NULL;
int lenA = 0;
int lenB = 0;
ListNode* cura = headA;
ListNode* curb = headB;
//求A链表的长度
while(cura != NULL)
{
cura = cura->next;
lenA++;
}
//求B链表的长度
while(curb != NULL)
{
curb = curb->next;
lenB++;
}
//找出长链和短链
int lenMax = lenA > lenB? lenA : lenB;
int lenMin = lenA <= lenB? lenA : lenB;
ListNode* headMax = lenA > lenB? headA : headB;
//ListNode* headMin = lenA < lenB? headA : headB;
ListNode* headMin = lenA <= lenB? headA : headB;
ListNode* curMax = headMax;
ListNode* curMin = headMin;
//移动curMax
curMax = headMax;
for(int i=0; i<lenMax-lenMin; i++)
curMax = curMax->next;
//找交叉点
while(curMax != NULL)
{
if(curMax==curMin) return curMax;
curMax = curMax->next;
curMin = curMin->next;
}
return NULL;
}
};
一个隐藏的坑：
为什么不能写成注释里的样子？
ListNode* headMax = lenA > lenB? headA : headB;
//ListNode* headMin = lenA < lenB? headA : headB;
ListNode* headMin = lenA <= lenB? headA : headB;
考虑一种特殊情况：当lenA=lenB时，则headMax = headB, headMin = headB，两个都一样了。所以不能写成注释里的样子
不过，当要赋的值时常数则无所谓，相等就相等呗
int lenMax = lenA > lenB? lenA : lenB;
int lenMin = lenA < lenB? lenA : lenB;
但是为了安全起见，以后统一写成：
int lenMax = lenA > lenB? lenA : lenB;
int lenMin = lenA <= lenB? lenA : lenB;
142.环形链表Ⅱ
mydemo——（成功）
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* slow= head;
ListNode* fast = head;
ListNode* index1 = head;
ListNode* index2;
//判断有无环，若有环则求出相遇点
do{
if(fast == NULL || fast->next == NULL)
return NULL;
else
{
fast = fast->next->next;
slow = slow->next;
}
}
while(fast != slow);
//求出环的入口
index2 = fast;
while(index1 != index2)
{
index1 = index1->next;
index2 = index2->next;
}
return index1;
}
};
小心一个坑,do-while语句最后是有一个 ；的；
do{
}
while();
卡哥demo
思路一致，但是卡哥的写法更简洁
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* slow= head;
ListNode* fast = head;
ListNode* index;
while(fast != NULL && fast->next != NULL)
{
fast = fast->next->next;
slow = slow->next;
if(fast==slow)
{
ListNode* index = fast;
while(head != index)
{
head = head->next;
index = index->next;
}
return index;
}
}
return NULL;
}
};