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

解题思路：

1，先利用快慢指针找到链表中间节点

2，将链表后半部分进行反转

3，将链表前半部分与反转后的后半部分进行合并

实现代码：

#include <iostream>
using namespace std;

/*
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}.
*/
struct ListNode {
     int val;
     ListNode *next;
     ListNode(int x) : val(x), next(NULL) {}
};
void addNode(ListNode* &head, int val)
{
    ListNode *node = new ListNode(val);
    if(head == NULL)
    {
        head = node;
    }
    else
    {
        node->next = head;
        head = node;
    }
}
void printList(ListNode *head)
{
    while(head)
    {
        cout<<head->val<<" ";
        head = head->next;
    }
}
class Solution {
public:
    void reorderList(ListNode *head) {
        if(head == NULL || head->next == NULL)
            return ;
        ListNode *quick = head;
        ListNode *slow = head;
        while(quick->next &&quick->next->next)//采用快慢指针查找链表中间节点，快指针走两步，慢指针走一步 
        {
            quick = quick->next->next;
            slow = slow->next;
        }
        quick = slow;
        slow = slow->next;
        quick->next = NULL;
        reverseList(slow);//将后半部分进行反转 
        
        quick = head;
        while(quick && slow)//将前半部分与反转后的后半部分进行合并 
        {
            ListNode *t = slow->next;
            slow->next = quick->next;
            quick->next = slow;
            slow = t;
            quick = quick->next->next;
        }
                       
    }
    void reverseList(ListNode* &head)//采用头插法进行链表反转 
    {
        if(head == NULL || head->next == NULL)
            return ;
        ListNode *p = head->next;
        head->next = NULL;
        while(p)
        {
            ListNode *t = p->next;
            p->next = head;
            head = p;
            p = t;
        }
    }
};
int main(void)
{
    ListNode *head = new ListNode(6);
    addNode(head, 5);
    addNode(head, 4);
    addNode(head, 3);
    addNode(head, 2);
    addNode(head, 1);
    addNode(head, 0);
    printList(head);
    cout<<endl;
    
    Solution solution;
    solution.reorderList(head);
    printList(head);
    
    return 0;
}