[LeetCode 143] Reorder List

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

Diffculty
Medium

Similar Problems

Analysis

思路：

我们可以先找到链表的中点（利用快慢指针），然后翻转链表的后半部分， 再和前半部分链接到一起。

举例：如1-2-3-4-5-NULL， 我们翻转4-5-NULL，将前半部分链表3-NULL, 然后链接1-2-3-NULL, 5-4-NULL,依次将后半部分翻转链表插入，得到1-5-2-4-3-NULL.'

// reverse链表时，一般我们会构造一个虚拟头结点来简化翻转过程，因为要从头到尾翻转， // 所以每次都是插入到虚拟头结点之后，最初的head被不断后移。 // 当然我们要首先判断后半部分链表是否符合翻转条件，或者是否存在节点。

class Solution { public: void reorderList(ListNode *head) { if(head == NULL || head->next == NULL) return;

    //(1) 找到链表的一半后一个结点
    ListNode* slow = head;
    ListNode* fast = head;
    while(fast != NULL && fast->next != NULL){
        slow = slow->next;
        fast = fast->next->next;
    }

    // 注意我们通过快慢指针，得到中间节点时，后半部分链表的头结点应该是slow->next。
    ListNode* reverseHead = slow->next;
    //（2）链接后一半的位置的节点作为链尾
    slow->next = NULL;
    //(3) 翻转后半段链表
    reverse_list(reverseHead);

    //(4) 链接两个链表， 先保存头结点head
    ListNode* cur = head;
    //翻转链表如果有节点 就继续链接
    while(reverseHead != NULL){
        //保存后半截链表后一个节点
        ListNode* tmp = reverseHead->next;
        //连接两链表
        reverseHead->next = cur->next;
        cur->next = reverseHead;
        //确定两个链表的链接的新起点
        reverseHead = tmp;
        cur = cur->next->next;
    }

    return;
}

private: //翻转链表 void reverse_list(ListNode &head){ if(head == NULL || head->next == NULL) return; ListNode dummyhead(0); dummyhead.next = head; ListNode p = head;

   while(p->next != NULL){
       ListNode* tmp = p->next;
       p->next = tmp->next;
       tmp->next = dummyhead.next;
       dummyhead.next = tmp;
   }

   head = dummyhead.next;
   return;
}

};