链表OJ--下

---

前言

一、链表分割

牛客网CM11：链表分割- - -点击此处传送

题解：
思路图：

代码：

二、环形链表I

力扣141：环形链表- - -点击此处传送

思路图:

扩展问题：

代码：

bool hasCycle(struct ListNode *head) {struct ListNode*fast=head,*slow=head;while(fast && fast->next){//slow走一步slow=slow->next;//fast走两步fast=fast->next->next;//若相等（相遇）则有环，返回true并退出程序if(fast==slow){return true;}}//否则无环return false;
}

三、环形链表II

力扣142：环形链表II- - -点击此处传送

题解：
思路图：

代码：

struct ListNode *detectCycle(struct ListNode *head) {struct ListNode*fast=head;struct ListNode*slow=head;while(fast && fast->next){slow=slow->next;fast=fast->next->next;if(fast==slow){struct ListNode*meet=slow;while(head != meet){head=head->next;meet=meet->next;}return meet;}}return NULL;
}

四、链表的回文结构

牛客网OR36：链表的回文结构- - -点击此处传送

思路图：

代码：

struct ListNode*reverseList(struct ListNode*head){struct ListNode*cur=head;struct ListNode*newhead=NULL;while(cur){struct ListNode*next=cur->next;cur->next=newhead;newhead=cur;cur=next;}return newhead;}struct ListNode*middleNode(struct ListNode*head){struct ListNode*slow=head;struct ListNode*fast=head;while(fast && fast->next){slow=slow->next;fast=fast->next->next;}return slow;}bool chkPalindrome(ListNode* head) {struct ListNode*mid=middleNode(head);struct ListNode*rhead=reverseList(mid);while(head && rhead){if(head->val != rhead->val)return false;head=head->next;rhead=rhead->next;}return true;}

五、随机链表的复制

力扣138：随机链表的复制- - -点击此处传送

思路图：

代码：

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;copy->next=cur->next;cur->next=copy;cur=copy->next;} cur=head;while(cur){struct Node*copy=cur->next;if(cur->random==NULL){copy->random=NULL;}else{copy->random=cur->random->next;}cur=copy->next;}cur=head;struct Node*newhead=NULL;struct Node*tail=NULL;while(cur){struct Node*copy=cur->next;struct Node*next=copy->next;if(tail==NULL){newhead=tail=copy;}else{tail->next=copy;tail=tail->next;}cur->next=next;cur=next;}return newhead;
}