重排链表避坑思考

这道重排链表也算是一道在学习链表这个知识点的中等偏上难度的题目。这道题一眼望去有一个非常直观的思路：

1.利用双指针截取最后一个节点，将其插入慢指针的next指针，将倒数第二个指针的next置空

2.慢指针往后走两个节点，快指针到倒数第二个。

不断遍历走就可以了，就不多做解释了，贴一个自己写的同思路的代码。

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ // typedef struct ListNode SL; // void reorderList(struct ListNode* head) // { // SL* slow=head; // SL* fast=head; // if(head->next==NULL) // { // return; // } // // int k=0; // while(fast->next&&fast->next->next) // { // SL* pcur=fast; // while(pcur->next->next) // //遍历找到倒数第二个节点 // { // pcur=pcur->next;//pcur是倒数第二个节点 // } // fast=pcur->next; // pcur->next=NULL; // fast->next=slow->next; // slow->next=fast; // slow=slow->next->next; // fast=fast->next; // }

这个思路也是非常简单而又粗暴，写的时候也是非常的自信啊。但是这个写法有一个问题，在数据量大的时候，处理时间也将是非常之长啊。

这个重排完的链表和需要插入的节点放在一起，我们的脑海里应该有一点非常抑制不住的想法，嗯，把要重排的截取下来，再倒装一下，嗯，再来一手快慢指针的间隔插入，诶，这不手到擒来，手拿把掐这道题了吗。非常的奈斯啊，但是，有一个问题出来了，我们从哪里能知道到底有几个节点需要重排。我也是非常的困惑啊，高中数学交了我们一个道理，思路受限的时候我们要回去思考一下这道题的本质了

嗯，首尾相加，0+n,1+(n-1),2+(n-2)，非常的直观昂，前后总和为n

依旧直观的可以得出一个答案，前后两下标和为n,那我们可以利用高中数学知识得出，均值为n/2，那么我们可以知道了，我们返回的节点位置就是中间节点，当然这个是偶数的情况下，如果是奇数个节点的时候我们思考一下，由一组两个数据（即前后和为n）的时候才调换，由简单的思考可得，奇数时的中间节点不做调换，重排结束的时候，这个中间节点就是尾节点了。至此，这道题我的思考路径就是如此了，从一开始的暴力解法到后续的优化过程就结束。感谢各位读者老爷的观看。

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ typedef struct ListNode SL; SL* middleNode(SL* head) { if(head==NULL) { return NULL; } //快慢指针一个走一步，一个走两步 SL* slow=head; //SL* fast=slow->next->next;链表就一个节点就不行，不能这样初始化 SL* fast=head; //SL* ret=NULL; while(fast->next&&fast->next->next)//均不为空 { fast=fast->next->next; slow=slow->next; } return slow; } SL* reverseList(SL* head) { SL* prev = NULL; SL* curr = head; while (curr) { SL* next = curr->next; curr->next = prev; prev = curr; curr = next; } return prev; } void reorderList(SL* head) { if(head==NULL||head->next==NULL) { return; } SL* slow=head; SL* fast=middleNode(head); SL* ps=fast; fast=fast->next; ps->next=NULL; //中间节点已经返回 SL* newhead=reverseList(fast); //反转完成，开始插入 SL* pcur=newhead; while(newhead) { newhead=pcur->next; pcur->next=slow->next; slow->next=pcur; slow=slow->next->next; pcur=newhead; } }