CM11 链表分割
题目
现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
题目链接：链表分割
解法
代码如下：
class Partition { public: ListNode* partition(ListNode* pHead, int x) { struct ListNode* lesstail=(struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* moretail=(struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* less=lesstail; struct ListNode* more=moretail; struct ListNode* cur=pHead; while(cur) { if(cur->val<x) { less->next=cur; less=less->next; cur=cur->next; } else { more->next=cur; more=more->next; cur=cur->next; } } more->next=NULL; less->next=moretail->next; pHead=lesstail->next; free(lesstail); free(moretail); return pHead; } };
这里的题，没有c语言选项，可以直接在c++里写也是没有问题的，因为c++兼容c的大部分代码，首先我们创建两个临时空间用于保存较小值和较大值的链表空间分别复制给less和more两个指针，将pHead复制给cur指针，然后利用循环将cur指针逐个遍历pHead中的结点值与val进行比较，较小值用less指向，较大值用more指向，最后more再指向NULL（此时more指向的应该是最后的结点），less指向moretail第一个结点，再将pHead指向lesstail第一个结点，再将两个临时空间释放，最后返回pHead即为分割好的链表。
OR36 链表的回文结构
题目
对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
测试样例：1->2->2->1
返回：true
题目链接：链表的回文结构
解法
代码如下：
class PalindromeList { public: bool chkPalindrome(ListNode* A) { struct ListNode*slow=A; struct ListNode*fast=A; while(fast->next) { slow=slow->next; fast=fast->next; } struct ListNode*change=NULL; struct ListNode*head=slow; while(head) { struct ListNode*next=slow->next; head->next=change; change=head;//重新置头 head=next; } while(slow) { if(A->val!=change->val) { return false; } slow=slow->next; change=change->next; } return true; } };
这个算法的思路是先建立两个快慢指针，fast指针走两步，slow指针走一步，当fast指针遍历完整个链表时，slow指向链表中间位置，再创建两个指针一个指向NULL，另一个复制slow当前地址，再将slow之后的链表进行反转，再比较，只要有一个值不相等即返回false，遍历后都相等，返回ture。
160. 相交链表
题目
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构。
题目链接：相交链表
解法
代码如下：
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { if (headA == NULL || headB == NULL) { return NULL; } struct ListNode *p, *q; for (p = headA, q = headB; p != q; ){ if (p != NULL) p = p->next; else p = headB; if (q != NULL) q = q->next; else q = headA; } return p; }
这种算法的主体思路为复制AB两个头结点指针，两个结点同时开始遍历，如果第一趟遍历不相等，那先到尾结点的指针先走到另一头结点的位置，之后另一个指针接着走一步，如果两指针不相等，就一直进入循环，直至两指针相等跳出循环，最后返回其中一个结点即为相交结点。
上述代码可改为下面的简洁形式：
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { if(headA==NULL||headB==NULL) return NULL; struct ListNode *p=headA,*q=headB; while(p!=q) { p=p==NULL?headB:p->next; q=q==NULL?headA:q->next; } return q; }
141. 环形链表
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
题目链接：环形链表
解法
代码如下：
bool hasCycle(struct ListNode* head) { if (head == NULL || head->next == NULL) { return false; } struct ListNode* slow = head; struct ListNode* fast = head->next; while (slow != fast) { if (fast == NULL || fast->next == NULL) { return false; } slow = slow->next; fast = fast->next->next; } return true; }
这里使用快慢指针的写法，slow指针从头开始，fast指针从第二个结点开始，首先在循环中，如果fast指针走到了NULL或下一结点为空，则直接返回false，如果是环状的，则fast指针走两步，slow指针走一步，最终两指针会相遇， 最后跳出循环，返回ture。
142. 环形链表 II
题目
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
题目链接：环形链表||
解析
代码如下：
struct ListNode* detectCycle(struct ListNode* head) { struct ListNode *slow = head, *fast = head; while (fast != NULL) { slow = slow->next; if (fast->next == NULL) { return NULL; } fast = fast->next->next; if (fast == slow) { struct ListNode* ptr = head; while (ptr != slow) { ptr = ptr->next; slow = slow->next; } return ptr; } } return NULL; }
这种解法思路延续上一题的快慢指针，只不过fast指针也是从头开始以及返回值改变了，遍历环形链表fast等于slow时，此时先判断slow是否等于头结点，如果等于头结点，则直接返回头结点，如果不等，则进入循环，各自走一步，直至相等，返回相等时的结点即为环结点。
138. 复制带随机指针的链表
题目
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。
题目链接：复制带随机指针的链表
解析
代码如下：
struct Node* copyRandomList(struct Node* head) { if(head == NULL) return NULL; struct Node* p = head; struct Node* phead = (struct Node*)malloc(sizeof(struct Node));//复制后要返回的链表头结点 struct Node* ph = phead;//复制phead结点 while(p)//p不为NULL则一直循环 { struct Node* tmp = p->next;//保存p的下一结点 ph->val = p->val;//复制值到pHead p->next = ph;//p指向ph ph->random = p->random;//复制random指针给ph ph->next = (struct Node*)malloc(sizeof(struct Node));//开辟下一结点空间 if(tmp) ph = ph->next;//为真表示后面还有结点，ph指向下一结点 else ph->next = NULL;//为假表示后面没结点了 p = tmp;//p指向p的下一结点 } ph = phead;//再复制phead到ph while(ph) { if(ph->random)//random指向空则不执行 ph->random = ph->random->next;//random指向的修正 ph = ph->next;//指向下一结点 } return phead; }
代码分析我写在注释中了，主要思路是，先将p(head)的val复制到ph(phead)，然后将p的next指向当前ph结点，然后将p当前的random复制给ph(phead)的random，遍历直至p指向空，再将ph(phead)的random指向修正，最后phead即为复制后的链表
可以结合作者画的草图理解一下：
这个图可能画的不好，小伙伴如果理解不了可以自己画一遍推一下代码，应该就可以理解了。
结语
这里的解法代码部分来自力扣官方和作者自己的解法，作者只是进行了详细的剖析和部分改动方便大家理解和提升自己，学会多角度观察问题，解决问题。
有兴趣的小伙伴可以关注作者，如果觉得内容不错，请给个一键三连吧，蟹蟹你哟！！！
制作不易，如有不正之处敬请指出
感谢大家的来访，UU们的观看是我坚持下去的动力
在时间的催化剂下，让我们彼此都成为更优秀的人吧！！！
