🔥博客主页： 小羊失眠啦.
🎥系列专栏：《C语言》 《数据结构》 《Linux》《Cpolar》
❤️感谢大家点赞👍收藏⭐评论✍️
文章目录
- 一、分割链表
- 二、回文链表
- 三、相交链表
- 四、环形链表 I
- 五、环形链表 II
- 六、链表的深度拷贝
一、分割链表
我们创建两条链表，把小于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开始】
本次的内容到这里就结束啦。希望大家阅读完可以有所收获，同时也感谢各位铁汁们的支持。文章有任何问题可以在评论区留言，小羊一定认真修改，写出更好的文章~~
