【数据结构】第四站：单链表力扣题（二）

目录

一、链表的回文结构

二、相交链表

三、环形链表

四、环形链表Ⅱ

五、复制带随机指针的链表

---

一、链表的回文结构

题目描述：链表的回文结构_牛客题霸_牛客网

对于这道题，如果没有前面的一些题的基础，是非常难做的，我们的思路是这样的，先找到链表的中间结点，然后从中间结点开始将后半段链表逆置，然后依次比较即可。所以这里就需要复用前面题目的函数了，代码如下所示

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:struct ListNode* middleNode(struct ListNode* phead){struct ListNode* fast=phead;struct ListNode* slow=phead;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;}return slow;}struct ListNode* reverse(struct ListNode* phead){struct ListNode* prev=NULL;struct ListNode* cur=phead;while(cur!=NULL){struct ListNode* next=cur->next;cur->next=prev;prev=cur;cur=next;}return prev;}bool chkPalindrome(ListNode* A) {// write code herestruct ListNode* phead=A;struct ListNode* middle=middleNode(phead);struct ListNode* NewHead=reverse(middle);struct ListNode* cur1=phead;struct ListNode* cur2=NewHead;while(cur2!=NULL){if(cur1->val==cur2->val){cur1=cur1->next;cur2=cur2->next;}else{return false;}}return true;}
};

二、相交链表

题目链接：力扣

对于这道题，我们可以采用最简单的双层暴力循环做出来。但是那样效率太低，我们其实可以先算出两个链表的长度，然后让长的链表都差值步，最后两个链表一块走，如果遇到两个结点的地址相同，那么就是相交的位置

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode* cur1=headA;struct ListNode* cur2=headB;int len1=0;int len2=0;while(cur1){len1++;cur1=cur1->next;}while(cur2){len2++;cur2=cur2->next;}cur1=headA;cur2=headB;if(len1>len2){int len=len1-len2;while(len--){cur1=cur1->next;}}else{int len=len2-len1;while(len--){cur2=cur2->next;}}while(cur1!=cur2){cur1=cur1->next;cur2=cur2->next;}return cur1;
}

三、环形链表

题目链接：力扣

对于这道题，我们可以采用快慢指针法来完成，试想一下，让快指针走两步，慢指针走一步，那么当慢指针走到环的入口的时候，快指针一定在环里面走了一段距离了，而每次快指针与满指针的距离都会缩短一步。那么一定会追的上。最终代码如下所示

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
bool hasCycle(struct ListNode *head) {struct ListNode* fast=head;struct ListNode* slow=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;if(fast==slow){return true;}}return false;
}

然而，我们在这里会思考一个问题，慢指针走一步，快指针走两步，如果带环，最后一定可以相遇吗，如果快指针走三步四步呢？

对于这个问题，我们需要好好思考一下。我们假定下面这样一个带环的链表

当fast走进环入口的时候，slow正好走到一半

当slow走到入口的时候，fast已经在环内某个位置了，我们不妨记作此时fast距离slowN步这样的话，由于距离每次减少1。所以N最终一定会减到0。所以会相遇

那么如果是fast一次三步呢？

我们还是上图进行分析

对于现在相差N步，由于每次距离减少2

所以当N为偶数的时候，一定会减为0

当N为奇数的时候，这时候fast就最终一定会超越slow一步，此时进入新一轮的追击

我们设周长为C,那么fast需要追C-1步

 这样的话当C-1为偶数的话，自然追的上，C-1为奇数的话，则永远也不可能追的上

当fast为一次走四步的时候也是同理的。

在这里我们或许还会碰到一个新的问题，如何计算环的长度，这个思路其实也很简单，我们只需要求出相遇点，然后让一个指针不动，另外一个指针一直走然后计数即可。当回到相遇点的时候，正好就是环的长度

四、环形链表Ⅱ

题目链接：力扣

对于这道题，我们可能就比较难以思考了。

我们的分析过程是这样的：

由于是环形链表，那么我们可以求出他的相遇点，既然有了相遇点。我们继续设相遇点与入口的距离为X，头节点与入口点的距离为L

 然后我们计算fast和slow两个指针在相遇的瞬间他们已经走的距离

fast的距离为L+N*C+X，其中N大于等于1。因为fast先入环需要追击一圈

slow的距离为L+X

注意这里slow在环内所走的路程一定不超过一圈，即0<=X<C，这是因为fast的速度是slow的二倍，假如fast追赶slow所需要的路程不超过C-1，由于相对速度为1，那么slow所走的路程就不超过C-1。

由于fast的速度是slow的二倍，所以fast的路程是slow的二倍。

所以 L+N*C+X=2(L+X)

可以得出，L=N*C-X

为了方便理解可以进一步化简为：L=(N-1)*C-X

这个公式的物理意义就是，一个指针从头结点开始走，一个指针从相遇点走，那么必然相遇于入口。代码为

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode *detectCycle(struct ListNode *head) {struct ListNode* fast=head;struct ListNode* slow=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;if(fast==slow){struct ListNode* meet=fast;while(meet!=head){meet=meet->next;head=head->next;}return meet;}}return NULL;
}

其实对于这道题，还有另外一种思路，我们可以将相遇点和相遇点的下一个结点断开，然后让相遇点的下一个结点作为头结点，这样就转化为了相交链表的问题

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode* cur1=headA;struct ListNode* cur2=headB;int len1=0;int len2=0;while(cur1){len1++;cur1=cur1->next;}while(cur2){len2++;cur2=cur2->next;}cur1=headA;cur2=headB;if(len1>len2){int len=len1-len2;while(len--){cur1=cur1->next;}}else{int len=len2-len1;while(len--){cur2=cur2->next;}}while(cur1!=cur2){cur1=cur1->next;cur2=cur2->next;}return cur1;
}
struct ListNode *detectCycle(struct ListNode *head) {struct ListNode* fast=head;struct ListNode* slow=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;if(fast==slow){struct ListNode* meet=fast;struct ListNode* list1=meet->next;struct ListNode* list2=head;meet->next=NULL;return getIntersectionNode(list1,list2);}}return NULL;
}

五、复制带随机指针的链表

题目链接：力扣

解法一

对于这道题，我们有一种比较简单的思路，直接暴力求解。

具体思路是首先将普通的链表拷贝下来。先不处理random指针。这个比较简单

然后，我们开始处理random，对于random我们只能采用相对位置来进行记录。这样的话，时间复杂度达到了O(N²)

我们直接给出代码

/*** Definition for a Node.* struct Node {*     int val;*     struct Node *next;*     struct Node *random;* };*/struct Node* copyRandomList(struct Node* head) {struct Node* copyhead=NULL;struct Node* copytail=NULL;struct Node* cur=head;while(cur){struct Node* copy=(struct Node*)malloc(sizeof(struct Node));copy->val=cur->val;copy->next=NULL;if(copyhead==NULL){copyhead=copytail=copy;}else{copytail->next=copy;copytail=copy;}cur=cur->next;}cur=head;struct Node* copycur=copyhead;while(cur){if(cur->random==NULL){copycur->random=NULL;copycur=copycur->next;}else{struct Node* cur2=head;int count=0;while(cur2!=cur->random){cur2=cur2->next;count++;}struct Node* copycur2=copyhead;while(count--){copycur2=copycur2->next;}copycur->random=copycur2;copycur=copycur->next;}cur=cur->next;}return copyhead;
}

解法二

我们可以不难看出上面的时间复杂度太大了，我们可以对上面的解法进行一点点的优化，我们采用指针数组先将每个random的地址给记录下来，最后在赋值这样也是可以的。但是仅仅只是优化了一点点。

解法三

想要真正的优化时间复杂度，那么我们必须要从思路开始下手了。

我们可以采用这样的思路：

首先这是我们的原来的链表

 我们可以在每一个结点的后面拷贝一个结点出来，如下图所示

最终形式如下图所示

 对于这个操作，其实是不难的

这部分的代码如下所示

 复制完成以后，我们接下来就要处理random了

最后一步就是，解开原链表 。

解开原来的链表，我们需要使用一个copyhead和copytail指针来管理copy链表，并且逐步解开解开

 

最终代码如下所示

/*** Definition for a Node.* struct Node {*     int val;*     struct Node *next;*     struct Node *random;* };*/struct Node* copyRandomList(struct Node* head) {//复制struct Node* cur=head; while(cur){struct Node* copy=(struct Node*)malloc(sizeof(struct Node));copy->val=cur->val;struct Node* next=cur->next;cur->next=copy;copy->next=next;cur=next;}//处理randomcur=head;while(cur){struct Node* copy=cur->next;if(cur->random==NULL){copy->random=NULL;}else{copy->random=cur->random->next;}cur=cur->next->next;}//解开两个链表cur=head;struct Node* copyhead=NULL;struct Node* copytail=NULL;while(cur){struct Node* copy=cur->next;struct Node* next=copy->next;if(copyhead==NULL){copyhead=copytail=copy;cur->next=next;}else{copytail->next=copy;copytail=copy;cur->next=next;}cur=next;}return copyhead;
}

---

本节内容到此为止

如果对你有帮助的话，不要忘记点赞加收藏哦！！！