[leetcode]reorder-list-蒲公英云

[leetcode]reorder-list

题目描述：

Given a singly linked list L: L 0→L 1→…→L n-1→L n,
reorder it to: L 0→L n →L 1→L n-1→L 2→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}.

实现思路：

For example,利用快慢指针找到中间节点，将链表分成前后两段，翻转后半段，然后再将两段合并，前一个后一个前一个后一个……这样子把后半段的插到前半段中去。

具体实现：

/**
 * 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 *fast = head;
        ListNode *slow = head;
        while(fast->next && fast->next->next){
            fast = fast->next->next;
            slow = slow->next;
        }
        //拆分链表，翻转后半部分链表
        ListNode *after = slow->next;
        slow->next = nullptr;
        ListNode *pre = nullptr;
        while(after){
            ListNode *temp = after->next;
            after->next = pre;
            pre = after;
            after = temp;
        }
        //合并两个链表
        ListNode *first = head;
        after = pre;
        while(first && after){
            ListNode *ftemp = first->next;
            ListNode *aftemp = after->next;
            first->next = after;
            first = ftemp;
            after->next = first;
            after = aftemp;
        }
    }
};