Given a singly linked list L: L0→L1→…→Ln-1→Ln,

reorder it to: L0→Ln→L1→Ln-1→L2→Ln-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}.

 

解题思路：

设置一个指针mid指向链表的中间结点；

将mid之后的半个链表进行反转，反转后的链表insert;

将insert中的结点挨个插入前半段链表中；

代码：

1 /** 2  * Definition for singly-linked list. 3  * struct ListNode { 4  *     int val; 5  *     ListNode *next; 6  *     ListNode(int x) : val(x), next(NULL) {} 7  * }; 8  */ 9 class Solution {10 public:11     void reorderList(ListNode* head) {12         if (!head || !head->next || !head->next->next)13             return;14         ListNode* ctrl = head;15         ListNode* mid = head;16         ListNode* insert = NULL;17         18         while (ctrl->next && ctrl->next->next) {19             ctrl = ctrl->next->next;20             mid = mid->next;21         }22         23         insert = reverseList(mid->next);24         mid->next = NULL;25         ctrl = head;26         27         while (insert) {28             ListNode* t = ctrl->next;29             ctrl->next = insert;30             insert = insert->next;31             ctrl->next->next = t;32             ctrl = t;33         }34         35         return;36     }37     38     ListNode* reverseList(ListNode* head) {39         if (!head->next)40             return head;41         ListNode* cur = NULL;42         ListNode* next = head;43         ListNode* left = NULL;44         while (next) {45             left = next->next;46             next->next = cur;47             cur = next;48             next = left;49         }50         return cur;51     }52 };