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. 而我的方法是把结尾连接下一个待翻转的结点。

// O(N) time, O(1) space in totalvoid reorderList(ListNode *head) {    if (!head || !head->next) return;    // find the middle node: O(n)    ListNode *p1 = head, *p2 = head->next;    while (p2 && p2->next) {        p1 = p1->next;        p2 = p2->next->next;    }    // cut from the middle and reverse the second half: O(n)    ListNode *head2 = p1->next;    p1->next = NULL;    p2 = head2->next;    head2->next = NULL;    while (p2) {        p1 = p2->next;        p2->next = head2;        head2 = p2;        p2 = p1;    }    // merge two lists: O(n)    for (p1 = head, p2 = head2; p1; ) {        auto t = p1->next;        p1 = p1->next = p2;        p2 = t;    }}

 

 

我的代码

void reorderList(ListNode *head) {        int len = 0; //链表长度        ListNode * p = head;        ListNode * latterpart = head;        //找链表长度        while(p != NULL)        {            len++;            p = p->next;        }        if(len <= 2)        {            return;        }        //把链表分成两份 如1 2 3 4 5 分成 1 2 3 和 4 5        len = (len + 1) / 2;  //一半的位置        p = head;        while(--len)        {            p = p->next;        }        latterpart = p->next;        p->next = NULL;        //翻转后半部分        ListNode * plast = latterpart;        while(plast->next != NULL)        {            p = plast->next;            plast->next = p->next;            p->next = latterpart;            latterpart = p; //更新头部 每次把后面的转到最前面去        }        //交叉前后两段        p = head;        while(p != NULL && latterpart != NULL) //如果前半部分和后半部分都还有可连接的 继续        {            ListNode * tmp = p->next;            p->next = latterpart;            latterpart = latterpart->next;            p->next->next = tmp;            p = p->next->next;        }        return;    }