給定一個單鏈表?L：L0→L1→…→Ln-1→Ln ，

將其重新排列后變為：?L0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是單純的改變節點內部的值，而是需要實際的進行節點交換。

示例?1:

給定鏈表 1->2->3->4, 重新排列為 1->4->2->3.

示例 2:

給定鏈表 1->2->3->4->5, 重新排列為 1->5->2->4->3.

?

思路：

根據題的意思，可以理解成，將鏈表分成兩半，將后一半倒著插入第一半當中，

那么就好辦了。

將后一半反轉，再合并。

?

class Solution {public:void reorderList(ListNode* head) {if (head == NULL)return;int len = 0;ListNode *head1 = head;while (head1){len++;head1 = head1->next;}if (len <= 2)return;int half = len / 2;int cnt = len - half;head1 = head;ListNode *last = NULL;while (cnt){cnt--;last = head1;head1 = head1->next;}last->next = NULL;ListNode *head2 = NULL;last = head1;head1 = head1->next;///last->next = NULL;while (head1 !=NULL){ListNode *node = head1 ->next;head1->next = last;last = head1;head1 = node;}head2 = last;while (head != NULL && head2 != NULL){//cout << "2" << endl;ListNode *next1 = head->next;ListNode *next2 = head2 -> next;head->next = head2;///head2->next = next1;head = next1;head2 = next2;}}};

?

轉載于:https://www.cnblogs.com/lMonster81/p/10433759.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的Leetcode143. Reorder List重排链表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。