一.反转链表
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为mid struct 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->val<=list2->val) //先把第一个给head和tail 保证不为空 { tail=list1; head=list1; list1=list1->next; } else { tail=list2; head=list2; list2=list2->next; } while(list1!=NULL&&list2!=NULL) //比较大小 小的尾插 { if(list1->val<=list2->val) { 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; }
