Reorder List leetcode_综合

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}.

分析：先用快慢指针找到链表的中点，然后翻转链表后半部分，再和前半部分组合。需要注意的是把链表分成两半时，前半段的尾节点要置为NULL，翻转链表时也要把尾节点置为NULL。代码如下

/*** 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 == nullptr || head->next == nullptr)return;ListNode* fast = head;ListNode* slow = head;while(fast->next != nullptr && fast->next->next != nullptr) {slow = slow->next;fast = fast->next->next;}fast = slow->next;slow->next = nullptr;fast = reverse(fast);slow = head;ListNode* slowNext;ListNode* fastNext;while(fast != nullptr) {slowNext = slow->next;fastNext = fast->next;fast->next = slow->next;slow->next = fast;slow = slowNext;fast = fastNext;}}ListNode* reverse(ListNode* head) {if(head == nullptr || head->next == nullptr)return head;ListNode* helper = new ListNode(0);helper->next = head;ListNode* pre = helper;ListNode* last = head;ListNode* cur = last->next;while(cur != nullptr) {last->next = cur->next;cur->next = pre->next;pre->next = cur;cur = last->next;}return helper->next;}
};