Reorder List

Description

Given a singly linked list L: L0 → L1 → … → Ln-1 → Ln
reorder it to: L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

Example
Given 1->2->3->4->null, reorder it to 1->4->2->3->null.

Challenge:
Can you do this in-place without altering the nodes' values?
We are here

Link

Lintcode_ladder

Method

1. divide the whole list into first and second part, we reverse the second part, then create a dummy list merging first and reversed second part by the order one, two, one ,two...
2. x

Example

1. 1

/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @return: void
     */
    void reorderList(ListNode *head) {
        // write your code here
        if (!head || !head->next) {
            return;
        }
        // find middle
        ListNode* mid = getmiddle(head);
        // reverse second part
        ListNode* back = reverse(mid->next);
        // disconnect first and second part
        mid->next = nullptr;
        // merge these two
        merge(head, back);
        return;
    }
private:
    ListNode* getmiddle(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head->next;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
    // standard reverse
    ListNode* reverse(ListNode* head) {
        // my solution, every time test head->next
        ListNode dummy(0);
        dummy.next = head;
        ListNode* prev = &dummy;
        while (head->next) {
            ListNode* tmp = head->next;
            head->next = tmp->next;
            tmp->next = prev->next;
            prev->next = tmp;
        }
        return dummy.next;
        // general solution, every time test head
        // ListNode* prev = nullptr;
        // while (head) {
        //     ListNode* tmp = head->next;
        //     head->next = prev;
        //     prev = head;
        //     head = tmp;
        // }
        // return prev;
    }
    // merge two into one
    void merge(ListNode* h1, ListNode* h2) {
        ListNode dummy(0);
        ListNode* tail = &dummy;
        int index = 0;
        while (h1 && h2) {
          if (index % 2 == 0) {
              tail->next = h1;
              h1 = h1->next;
          } else {
              tail->next = h2;
              h2 = h2->next;
          }
          index++;
          tail = tail->next;
        }
        if (h1) {
            tail->next = h1;
        } else {
            tail->next = h2;
        }
    }
};

Similar problems

x

Tags

x