原题

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

分析

将链表结点按照第一个 倒数第一个 第二个 倒数第二个 的顺序重新排序

如 1 2 3 4重新排序后是 1 4 2 3

AC代码

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     ListNode *next;

 *     ListNode(int x) : val(x), next(NULL) {}

 * };

 */

class Solution {

public:

    //翻转链表

    ListNode *reverse(ListNode *head){

        if(!head) return;

        ListNode * pre = NULL;

        while(head){

            ListNode * nex = head->next;

            head->next = pre;

            pre = head;

            head = nex;

        }

        return pre;

    }

    void reorderList(ListNode* head) {

        if(!head || !head->next) return head;

        ListNode * fast = head;

        ListNode * slow = head;

        while(fast->next && fast->next->next){

            fast = fast->next->next;

            slow = slow->next;

        }

        fast = slow->next;

        //截断

        slow->next = NULL;

        //翻转后半段

        ListNode * p = reverse(fast);

        //合并

        ListNode * res = head;

        ListNode * q = head->next;

        while(p && q){

            res->next = p;

            p = p->next;

            res = res->next;

            res->next = q;

            q = q->next;

            res = res->next;

        }

        if(p) res->next = p;

        if(q) res->next = q;

    }

};