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.

http://www.lintcode.com/en/problem/reorder-list/#

Discussion

1. use a pair of fast-slow pointers to figure out the mid position of the list.
2. reverse the second half.
3. merge the first half and the second half one by one.

Solution

class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @return: void
     */
    void reorderList(ListNode *head) {
        // write your code here
        if(head == NULL || head->next==NULL) return;
        ListNode *list1 = head;
        ListNode *list2 = head;
        ListNode *preList2 = head;
        while(list1 !=NULL && list1->next !=NULL) {
            list1 = list1->next->next;
            preList2 = list2;
            list2 = list2->next;
        }
        preList2->next = NULL;
        list2 = reverse(list2);
        merge(head, list2);
    }
private: 
    ListNode* reverse(ListNode *head) {
        ListNode *pre = NULL;
        ListNode *cur = head;
        while(cur != NULL) {
            ListNode *tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        //head = pre;//刚开始定义成void类型函数，将head更新，这样是不对的，因为head不是引用传值或者地址传值，它只是表示头指针。
        return pre;
    }
    void merge(ListNode *list1, ListNode *list2) {
        ListNode *cur1 = list1, *cur2 = list2;
        if(list1 == NULL) {list1 = list2 ; return;}
        if(list2 == NULL) return;

        while(cur1->next != NULL) {
            ListNode *tmp1 = cur1->next;
            ListNode *tmp2 = cur2->next;
            cur1->next = cur2;
            cur2->next = tmp1;
            cur1 = tmp1;
            cur2 = tmp2;
        }
        cur1->next = cur2;
    }

};