leetcode 143.重排链表

题干

给定一个单链表 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.

题解

笨比代码 * 抽象双指针 * 在把尾结点插入的时候原先倒数第二个节点会导致成环，重新寻找尾结点后要将next置nullptr

class Solution { public: void reorderList(ListNode* head) { if(head==nullptr) return; //尾节点 ListNode* tail = head; ListNode* eternalHead = head; while(tail->next!=nullptr){ tail = tail->next; } if(head->next==tail) return; while(head!=tail){ tail->next = head->next; head->next = tail; //cout<<head->val<<' '<<head->next->val<<' '<<head->next->next->val<<endl; //cout<<tail->val<<' '<<tail->next->val<<endl; while(tail->next!=head->next){ //cout<<tail->val<<' '<<"looping"<<endl; tail = tail->next; //cout<<"looping"<<' '; } //cout<<tail->val<<endl; tail->next = nullptr; head = head->next->next; //cout<<head->val<<' '<<tail->val<<endl; if(head->next==tail) break; } return; } }; //1 4 2 3 //h t //h t // h t // p h t //1 2 3 4 5 6 //h t //1 6 2 3 4 5 //h t //h t // h t //1 6 2 5 3 4 // h t // h t // h t //1 2 3 4 5 //h t //1 5 2 3 4 //h t //h t // h t //1 5 2 4 3 // h t // h t

或者可以将原本的单链表读出存入线性表，在反复遍历头尾元素来重新构建单链表 * 注意最后一个循环break的位置和指针移动的顺序

class Solution { public: void reorderList(ListNode* head) { if(head==nullptr) return; vector<ListNode *> linarList; ListNode* ptr = head; while(ptr!=nullptr){ linarList.push_back(ptr); ptr = ptr->next; } int j = linarList.size() - 1; int i = 0; while(i<j){ linarList[i]->next = linarList[j]; i++; if(i==j) break; linarList[j]->next = linarList[i]; j--; } linarList[i]->next = nullptr; return; } };