＜数据结构＞五道LeetCode链表题分析.环形链表，反转链表，合并链表，找中间节点.

目录

一.反转链表

1.头插法

2.迭代法

二.链表的中间节点

1.快慢指针法

2.指针数组法

三.合并两个有序链表

尾插法

四.环形链表（1）

快慢指针法

五.环形链表（2）

思路分析：

代码实现：

一.反转链表

1.头插法

//头插法struct ListNode* reverseList(struct ListNode* head){if(head==NULL){return NULL;}struct ListNode*newhead=NULL;struct ListNode*next=head->next;while(head!=NULL){ next=head->next; head->next=newhead;//将head头查到newhead上 newhead=head;//newhead为新的头 head=next;//head 接着往下走}return newhead;}

2.迭代法

//迭代法struct ListNode* reverseList(struct ListNode* head){if(head==NULL||head->next==NULL){return head;}struct ListNode*n1=NULL; //利用三个指针 循环往下走struct ListNode*n2=head; //来调转链表指向struct ListNode*n3=n2->next; while(n3->next!=NULL){n2->next=n1;n1=n2;n2=n3;n3=n2->next;}n2->next=n1;n3->next=n2;return n3;}

二.链表的中间节点

1.快慢指针法

//快慢指针法:fast指针一次走两步，slow指针一次走一步，//当fast为NULL或fast->next为NULL时(分奇偶)，此时的slow为midstruct ListNode* middleNode(struct ListNode* head){struct ListNode*slow=head;struct ListNode*fast=head;while(fast!=NULL&&fast->next!=NULL){fast=fast->next->next;slow=slow->next;}return slow;}

2.指针数组法

//不推荐此方法 空间复杂度为O(N)struct ListNode* middleNode(struct ListNode* head){ struct ListNode*arr[100]={NULL};int count=0;struct ListNode*p1=head;while(p1!=NULL){arr[count]=p1;count++;p1=p1->next;}return arr[count/2];}

三.合并两个有序链表

尾插法

//尾插法：创建一个新的头，比较大小，小的尾插到后面struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){if(list1==NULL) // 特殊情况 return list2;if(list2==NULL) return list1;struct ListNode*head=NULL;struct ListNode*tail=NULL;if(list1->valval) //先把第一个给head和tail 保证不为空{tail=list1;head=list1;list1=list1->next;}else{tail=list2;head=list2;list2=list2->next;}while(list1!=NULL&&list2!=NULL)//比较大小 小的尾插{if(list1->valval){tail->next=list1;tail=tail->next;list1=list1->next;}else{tail->next=list2;tail=tail->next;list2=list2->next;}}if(list1==NULL)//最后有一个到头，直接接上后面{tail->next=list2;}else{tail->next=list1;}return head;}

四.环形链表（1）

快慢指针法

//先让fast进入循环，然后slow进入，最后fast与slow相遇bool hasCycle(struct ListNode *head){struct ListNode *slow=head;struct ListNode *fast=head;while(fast!=NULL&&fast->next!=NULL){slow=slow->next;fast=fast->next->next;if(fast==slow){return true;}}return false;}

五.环形链表（2）

思路分析：

代码实现：

//快慢指针struct ListNode *detectCycle(struct ListNode *head) {struct ListNode *slow=head;struct ListNode *fast=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;if(fast==slow) //先快慢指针相遇{struct ListNode *meet=slow;while(meet!=head){meet=meet->next; //再一个从meet走，一个从head走head=head->next;}return head; //相遇时为环形链表的入口}}return NULL;}