一、链表的回文结构
题目描述：链表的回文结构_牛客题霸_牛客网
对于这道题，如果没有前面的一些题的基础，是非常难做的，我们的思路是这样的，先找到链表的中间结点，然后从中间结点开始将后半段链表逆置，然后依次比较即可。所以这里就需要复用前面题目的函数了，代码如下所示
/* 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 here struct 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; } //处理random cur=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; }
本节内容到此为止
如果对你有帮助的话，不要忘记点赞加收藏哦！！！
