24 交换链表节点
题目链接
方案一:自己的方案
奇偶节点,思路比代码随想录中的更直观一些,但是需要进行分类讨论,设置的辅助节点也多一些。
/**
* 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) {
// 空链表或者链表length = 1
if(!head || !head->next)
return head;
// length >= 2
// 设置虚拟头节点且保存交换后的头结点
ListNode* dummyHead = new ListNode(0, head);
// 设置pre和curr节点,其中pre是奇数节点,curr是pre下一个偶数节点
ListNode* pre = head;
ListNode* curr = pre->next;
ListNode* tmp = dummyHead;
// 返回的头结点 newhead
head = curr;
while(pre && pre->next){
curr = pre->next;
// 交换pre和curr节点
pre->next = curr->next;
curr->next = pre;
tmp->next = curr;
tmp = pre;
pre = pre->next;
}
return head;
}
};
方案二:代码随想录
直接上图:
需要注意的是要保存1,2,3节点,因为在改变next指针时很容易将链表断开。
/**
* 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* dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode* curr = dummyHead;
while(curr->next && curr->next->next){
ListNode* tmp1 = curr->next;
ListNode* tmp2 = tmp1->next;
ListNode* tmp3 = tmp2->next;
curr->next = tmp2;
tmp2->next = tmp1;
tmp1->next = tmp3;
curr = tmp1;
}
return dummyHead->next;
}
};
19删除链表倒数第n个节点
题目链接
- 方案一:两边扫描,第一遍得到链表长度length,倒数n==正数length-(n-1)
- 方案二:fast指针先于slow指针n步,fast到null时,slow是待删除节点
/**
* 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) {
// 两次扫描
// 第一次扫描得到链表长度lengthlength
// 倒数n == 正数 length-(n-1)
// 使用pre,curr删除节点
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode* pre = dummyHead;
ListNode* curr = head;
int length = 0;
while(curr){
length += 1;
curr = curr->next;
}
curr = head;
// curr 的index [1, length]
for(int index = 1; index < length - (n - 1); index++){
pre = curr;
curr = curr->next;
}
// 删除
pre->next = curr->next;
delete curr;
curr = nullptr;
return dummyHead->next;
}
};
/**
* 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) {
// fast指针比slow指针先行n步
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode* pre = dummyHead;
ListNode* curr = pre->next;
for(int count = 1; count < n; count++){
curr = curr->next;
}
while(curr->next){
pre = pre->next;
curr = curr->next;
}
// 删除待删除节点
ListNode* tmp = pre->next;
pre->next = tmp->next;
delete tmp;
return dummyHead->next;
}
};
面试题 链表相交
题目链接
-
方案一:双层for循环
-
方案二:O(n),直接上图:需要注意的是要考虑A,B哪个更长一些,可以通过swap讲currB指向更长的链表。
/**
* 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) {
// 两层for循环
ListNode* dummyHeadA = new ListNode(0, headA);
ListNode* dummyHeadB = new ListNode(0, headB);
for(ListNode* currA = dummyHeadA; currA->next; currA = currA->next){
for(ListNode* currB = dummyHeadB; currB->next; currB = currB->next){
if(currA->next == currB->next)
return currA->next;
}
}
return NULL;
}
};
/**
* 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) {
// 计算AB长度,末尾对齐
int lengthA = 0;
int lengthB = 0;
ListNode* currA = headA;
ListNode* currB = headB;
for(; currA; currA = currA->next)
lengthA += 1;
for(; currB; currB = currB->next)
lengthB += 1;
currA = headA;
currB = headB;
// 交换,使得currA指向最短链表
if(lengthA > lengthB){
swap(lengthA, lengthB);
swap(currA, currB);
}
// B向前移动lengthB-lengthA位置
for(int offset = 0; offset < lengthB - lengthA; offset++){
currB = currB->next;
}
while(currA){
if(currA == currB)
return currA;
else{
currA = currA->next;
currB = currB->next;
}
}
return NULL;
}
};
142环形链表II
题目链接文章来源:https://www.toymoban.com/news/detail-598169.html
这题完全求助于Carl大佬(双层for循环会超出时间限制), 神奇的思路,神奇的数学啊。文章来源地址https://www.toymoban.com/news/detail-598169.html
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
// 快慢指针,同时从head出发,fast每次移动2位,slow每次移动1位
// 若有环,则相遇
ListNode* fast = head;
ListNode* slow = head;
while(fast && fast->next){
slow = slow->next;
fast = fast->next->next;
if(fast == slow){
ListNode* tmp1 = fast;
ListNode* tmp2 = head;
while(tmp1 != tmp2){
tmp1 = tmp1->next;
tmp2 = tmp2->next;
}
return tmp1;
}
}
return NULL;
}
};
到了这里,关于day4_24交换链表节点_19删除节点_面链表相交_142环形链表II的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!