专题: 链表题目总结

作者 Lucyyang 日期 2020-03-08
专题: 链表题目总结

sd0061:"你超级厉害,只要再学会CS的算法和三大项,就无敌啦!"

开始重新刷起Leetcode啦,距离上学会有一段比较长的时间,于是这次打算彻彻底底的好好刷题学算法。那么就从链表总结起来吧。

链表的结构

struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {} //构造函数
};

反转链表

题目:Reverse Linked List

方法:这道题要注意设p1时令其等于null,这样反转之后,原本是头的next就会接到null。p2始终为原序例中p1的next,用于后面反转:将p2->next = p1。这样以来就有个问题,p2的next就无法找到了,所以我们在变化p2->next时,要先用一个ptmp存储原序列中的p2->next。

代码:

class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head == nullptr)
return nullptr;
ListNode *p1, *p2;
p1 = nullptr;
p2 = head;
while(p2 != nullptr) {
ListNode *ptmp = p2->next;
p2->next = p1;
p1 = p2;
p2 = ptmp;
}
return p1;
}
};

找到链表的中点

题目:设链表节点个数为n,如果n为偶数,那么返回第n/2+1个节点。

方法:采用快慢指针,快指针每次走两个节点,慢指针每次走一个节点,那么当快指针走到末尾后,慢指针正好在链表中点

代码:

class Solution {
public:
ListNode* midList(ListNode* head) {
if(head == nullptr)
return nullptr;
ListNode *fast, *slow;
fast = head;
slow = head;
while(fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
};

找到链表环的入口

题目:给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。

方法:1.通过快慢指针的方法,先找到环中的一个节点;2.慢指针从头开始,快指针从相遇节点处,每次同时只走一个节点,最后相遇处即为环中入口。

证明: 示意图

相遇时,快指针路程=a+(b+c)k+b ,k>=1 其中b+c为环的长度,k为绕环的圈数(k>=1,即最少一圈,不能是0圈,不然和慢指针走的一样长,矛盾)。 慢指针路程=a+b。

快指针走的路程是慢指针的两倍,所以: (a+b*2=a+(b+c)k+b 化简得: a=(k-1)(b+c)+c 这个式子的意思是: 链表头到环入口的距离=相遇点到环入口的距离+(k-1)圈环长度。其中k>=1,所以k-1>=0圈。所以两个指针分别从链表头和相遇点出发,最后一定相遇于环入口。

代码:

class Solution {
public:
ListNode* EntryNodeOfLoop(ListNode* pHead)
{
if(pHead == nullptr)
return nullptr;
else if(pHead->next == nullptr)
return nullptr;
ListNode *slow, *fast;
slow = pHead;
fast = pHead;
//求环中的一个点
while(fast != nullptr && fast->next != nullptr){
slow = slow->next;
fast = fast->next->next;
if(slow == fast)
break;
}
cout<<slow->val;
//求入口
if(!fast||!fast->next)return NULL;
slow = pHead;
while(slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
}
};

变换链表顺序

题目: Reorder List

方法:这个题目可以拆分成三个小问:1.将链表拆成前面一半和后面一半(快慢指针);2.将后面一半的链表进行反转(反转链表);3.将后面一半的链表合并到前面一半的链表中。

class Solution {
public:
void reorderList(ListNode* head) {
if(head == nullptr)
return;
else if(head->next == nullptr)
return;
ListNode *fast, *slow;
fast = head;
slow = head;
ListNode *pre;
// 快慢指针分割
while(fast != nullptr && fast->next != nullptr){
fast = fast->next->next;
pre = slow;
slow = slow->next;
}
pre->next = nullptr;
fast = head;
// 反转后半部分链表
ListNode *p1 = nullptr;
ListNode *p2 = slow;
while(p2!= nullptr){
ListNode *tmp = p2->next;
p2->next = p1;
p1 = p2;
p2 = tmp;
}
slow = p1;
fast = head;
//slow is the head of last part
// 进行拼接 slow的节点数最多比fast的多一个
ListNode *Lnext, *Fpre;
while(fast != nullptr){
Lnext= slow;
slow = slow->next;
Lnext->next = fast->next;
fast->next = Lnext;
Fpre = fast->next;
fast = fast->next->next;
}
Fpre->next= slow; // 不要忘了可能还有slow的最后一个元素
}
};

删除链表中重复的节点1

题目:如果链表为1->2->2->3->3->4,请返回1->2->3->4。

方法:比较简单,直接判断p1和p2(p1->next)值是否相同,相同则p2后移,直到找到不通的值时,再将p1->next连接到p2。注意:只有在p1和p2值不相同的时候,才进行连接,并二者都后移一个节点

代码:

class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode *p1, *p2, *p;
if(head == nullptr)
return nullptr;
p1 = head;
p2 = head->next;
p = p1;
while(p2 != nullptr){
if(p2->val == p1->val) {
p2 = p2->next;
p1->next = nullptr;
}else {
p1->next = p2;
p1 = p1->next;
p2 = p2->next;
}
}
return p;
}
};

删除链表中重复的节点2

题目:如果链表为1->2->2->3->3->4,请返回1->4。

方法:这个题目的和上一题的不同之处在于,是要删除全部的重复节点。注意设一个pNewHead,方便对特殊情况的处理。设p1,p2两个指针,p1指向当前准备连接next的节点,p2用于探查节点和节点的next是否值相同。如果节点和后一个节点值相同,则p2一直跳到第一个不相同的节点处,并将p1->next指向p2。 注意:我们不在之前的步骤中进行p1和p2节点的后移,全部放在当发现p2值和p2->next值不同时一起处理。如果p2->next和p2值不通,那么不论是因为在上一步进行了删去重复节点并进行连接的处理还是本来二者之间都没有重复节点,p1->next都已指向p2,因此直接后移即可。

代码:

class Solution {
public:
ListNode* deleteDuplication(ListNode* pHead)
{
if(pHead == NULL)
return nullptr;
ListNode *pNewHead = new ListNode(0);
ListNode *p1, *p2;
pNewHead->next = pHead; //忘记连接了
p1 = pNewHead;
p2 = pHead;
while(p2 != nullptr && p2->next != nullptr) { //后面要用到p2
if(p2->val == p2->next->val) {
int val = p2->val;
while(p2!= nullptr && p2->val == val) {
p2 = p2->next;
}
p1->next = p2;
//保持了p2比p1往前一个的状态,进入下一次的循环
}else {
//则p1本身next就与p2进行了连接
p1 = p2;
p2 = p2->next;
}
}
pNewHead = pNewHead->next;
return pNewHead;
}
};

合并K个链表

题目:L23,给定K个已经排好序的链表,合并成一个有序链表。

方法1:自己的方法比较暴力,直接遍历所有值放在一个vector中,然后进行排序,再连接成一个链表。复杂度比较高,O(K*N)。

代码:

class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
vector<int> vals;
for(auto itL:lists){
while(itL != NULL){
vals.push_back(itL->val);
itL = itL->next;
}
}
sort(vals.begin(), vals.end());
ListNode *lhead, *l3 = new ListNode(0);
lhead = l3;
for(auto it:vals){
l3->next = new ListNode(it);
l3 = l3->next;
}
return lhead->next;
}
};

方法2://TODO 研究下重载函数