重排链表（LeetCode）

题目链接

题目描述

给定一个单链表 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) return; ListNode *slow=head,*fast=head; while(fast->next&&fast->next->next){ slow=slow->next; fast=fast->next->next; } ListNode *p=slow->next,*pre=NULL; slow->next=NULL; while(p){ ListNode *tmp=p->next; p->next=pre; pre=p; p=tmp; } ListNode *h=new ListNode(0),*ans=h; while(head||pre){ if(head){ h->next=head; h=h->next; head=head->next; } if(pre){ h->next=pre; h=h->next; pre=pre->next; } } } };

---

2021.2.23：三刷

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: void reorderList(ListNode* head) { if(!head) return; ListNode *slow=head,*fast=head; while(fast->next&&fast->next->next){ slow=slow->next; fast=fast->next->next; } ListNode *p=slow->next,*h,*pre=NULL; slow->next=nullptr; while(p){ ListNode *tmp=p->next; p->next=pre; pre=p; p=tmp; } h=pre; while(head||h){ if(head){ p=head->next; head->next=h; head=p; } if(h){ p=h->next; h->next=head; h=p; } } } };