一、分割链表
我们创建两条链表，把小于x的节点放在一条链表中，剩余的放在另一条节点，最后将两条链表连接起来。在这里要使用带哨兵位的链表，不用考虑头插和第一条链表为空的问题，可以大大减少代码量。
class Partition { public: ListNode* partition(ListNode* pHead, int x) { struct ListNode* lessHead=(struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* lesstail=lessHead; struct ListNode* greaterHead=(struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* greatertail=greaterHead; struct ListNode* cur=pHead; while(cur) { if(cur->val < x) { lesstail->next=cur; lesstail=cur; } else { greatertail->next=cur; greatertail=cur; } cur=cur->next; } greatertail->next=NULL; lesstail->next=greaterHead->next; free(greaterHead); struct ListNode* newnode=lessHead->next; free(lessHead); return newnode; } };
注意：要将链表最后一个节点的指针域置为空，不然会导致链表循环。
二、回文链表
思路：首先找到链表的中间的地址（奇数个）或者是中间的第二个地址（偶数个）作为第二个链表的头，然后逆置第二个链表，然后第原始链表和第二个链表进行比较。（当原始链表和第二个链表有一个是空的时候，就可以跳出循环，说明是回文链表
struct ListNode* MidNode(struct ListNode* Head) { struct ListNode* slow=Head,*fast=Head; while(fast&&fast->next) { slow=slow->next; fast=fast->next->next; } return slow; } struct ListNode* RevNode(struct ListNode* Head) { struct ListNode* prev=NULL,*cur=Head; while(cur) { struct ListNode* next=cur->next; cur->next=prev; prev=cur; cur=next; } return prev; } class PalindromeList { public: bool chkPalindrome(ListNode* A) { // write code here struct ListNode* B=MidNode(A); B=RevNode(B); while(A&&B) { if(A->val==B->val) { A=A->next; B=B->next; } else { return false; } } return true; } };
三、相交链表
思路1：A链表每一个节点和B链表依次比较，如果有相等，就是相交，第一个相等的就是交点。
（判断是否是相交，交点是多少）时间复杂度：O(M*N)
思路2：当尾节点的地址相同的时候，就是相交。（判断是否是相交）
求出两个链表的长度，然后链表长的先走两个链表的差值，然后两个链表一起走，当地址相同的时候，位置就是节点（交点是多少）时间复杂度：O(M+N)
truct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode* curA=headA,*curB=headB; int lenA=0,lenB=0; while(curA->next) { curA=curA->next; lenA++; } while(curB->next) { curB=curB->next; lenB++; } if(curA!=curB) return NULL; int gap=abs(lenA-lenB); struct ListNode* shortList = headA; struct ListNode* longList = headB; if(lenA>lenB) { shortList=headB; longList=headA; } while(gap--) { longList=longList->next; } while(longList&&shortList) { if(longList==shortList) return shortList; longList=longList->next; shortList=shortList->next; } return NULL; }
注意：
- 地址相同，不是值相等（值相等不一定是节点）
- 编译器执行的是语法错误，编译器不能检查出执行逻辑，所以在最后要加上return NULL（因为上面有一个if之后返回一个值，编译器会认为不满足这个if条件的时候没有返回值）;
四、环形链表 I
[快慢指针]slow一次走一步，fast一次走两步，当slow进环之后，开启追赶模式，最后fast追上slow；不带环fast->next或者fast就会是NULL，带环的话就不会是NULL；
bool hasCycle(struct ListNode* head) { struct ListNode* slow = head, * fast = head; while (fast && fast->next) { fast = fast->next->next; slow = slow->next; if (slow == fast) { return true; } } return false; }
注意：刚开始fast等于slow，所以再循环里面先赋值，后比较
- slow一次走一步,fast一次走两步，一定能追上。
当slow走一半的时候，fast开始进环。此时两者的距离为N，每次之后，距离会减少1，所以就一定能追上。【距离为0，追上】 - slow一次走一步,fast一次走三步，不一定能追上。
当slow走1/3的时候，fast开始进环。此时两者的距离为N，每次之后，距离会减少2，如果距离为奇数，就会错过，【偶数可以追上】，此时距离又为环数-1【偶数追上，奇数就永远追不上】，所以不一定能追上。
五、环形链表 II
假设，进入环之前的距离为L；slow两者相遇后之前，进入环之后走的距离x；进入环之后两者的距离为N ；环的长度为C [快慢指针]slow一次走一步，fast一次走两步，fast是slow的两倍【slow绝对不会走一圈被fast追上，而是没有走一圈就被fast给追上了，因为当slow进入环之后，两者的距离为N，N肯定小于环数，所以两者相遇的时候，slow肯定没有走完一圈，所以slow走得距离为进入环之前的距离L+两者相遇后之前，进入环之后走的距离x即L+x;fast走的距离为n*C+L+x; n*C+L+x=2(L+x),---->n*C=L+x;n为未知数】【slow进环之后，fast不可能走完一圈】n*C=L+x:能证明，一个从进入链表走，一个从相遇的那个节点走，slow和fast在环入口处相遇。
struct ListNode *detectCycle(struct ListNode *head) { if(head==NULL || head->next==NULL) return NULL; struct ListNode* slow=head,*fast=head; while(fast&&fast->next) { slow=slow->next; fast=fast->next->next; if(slow==fast) { struct ListNode* meet=slow; while(slow!=head) { slow=slow->next; head=head->next; } return slow; } } return NULL; }
六、链表的深度拷贝
truct Node* copyRandomList(struct Node* head) { struct Node* cur =head; while(cur) { struct Node* copy=(struct Node*)malloc(sizeof(struct Node)); struct Node* next=cur->next; cur->next=copy; copy->val=cur->val; copy->next=next; cur=next; } cur=head; while(cur) { struct Node* copy=cur->next; if(cur->random!=NULL) { copy->random=cur->random->next; } else { copy->random=NULL; } cur=copy->next; } cur=head; struct Node* copyHead=NULL; struct Node* copyTail=NULL; while(cur) { struct Node* copy=cur->next; struct Node* next=copy->next; if(copyTail==NULL) { copyHead=copyTail=copy; } else { copyTail->next=copy; copyTail=copyTail->next; } cur->next=next; cur=cur->next; } return copyHead; }
思路：拷贝每一个节点连接在原节点之后，链接拷贝节点的random，新的random在前面的random的next。最后，把拷贝节点解下来，链接起来。【索引从0开始】
本次的内容到这里就结束啦。希望大家阅读完可以有所收获，同时也感谢各位铁汁们的支持。文章有任何问题可以在评论区留言，小羊一定认真修改，写出更好的文章~~
