Leetcode Reorder List

Given a singly linked list L: L₀?L₁?…?L_n-1?L_n, reorder it to: L₀?L_n?L₁?L_n-1?L₂?L_n-2?…

You must do this in-place without altering the nodes' values.

For example, Given {1,2,3,4}, reorder it to {1,4,2,3}.

先通过快慢指针找到转换节点，将转换节点后半部分逆序，然后再将转换节点依次插入前半部分即可。

代码如下：

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: void reorderList(ListNode* head) { if(!head || !head->next) return; ListNode* p1,*p2; p1 = p2 = head; while(p2->next && p2->next->next) { p1 = p1->next; p2 = p2->next->next; } ListNode* cur = p1->next; ListNode* next; while(cur->next) { next = cur->next; cur->next=next->next; next->next = p1->next; p1->next = next; } p2 = head; cur = p1->next; while(p2!=p1) { p1->next = cur->next; cur->next = p2->next; p2->next = cur; p2 = cur->next; cur = p1->next; } } };