leetcode解题: Reorder List (143)

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：Hashmap + two pointers O(N) Time with O(N) space

用一个hashmap记录每一个node的位置，map的key是位置的坐标。然后用双指针重新把list按顺序连接起来。
C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        if (head == NULL) {
            return;
        }
        unordered_map<int, ListNode*> map;
        int count = 0;
        while (head != NULL) {
            ListNode* cur = head;
            head = head->next;
            cur->next = NULL;
            map.insert({count, cur});
            count++;
        }
        ListNode* dummy = new ListNode(0);
        ListNode* tail = dummy;
        for (int i = 0, j = count - 1; i <= j; ++i, --j) {
            if (i == j) {
                tail->next = map[i];
                tail = tail->next;
            } else {
                tail->next = map[i];
                tail = tail->next;
                tail->next = map[j];
                tail = tail->next;
            }
        }

        ListNode* res = dummy->next;
        head = res;
    }
};

Java

解法2： findMiddle + Reverse O(N) Time + O(1) Space

本题也可以用linkedlist的常用算法解决。
第一步可以先找出list的中点，如果是偶数个如：1->2->3-4, 找出的是2，如果是奇数个：1->2->3->4->5, 找出的是3。
第二步：找出以后对后半部分进行reverse操作。
第三步：将右半部份merge到左半部分
这种解法不像第一种解法需要额外的存储空间。
C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        if (head == NULL || head->next == NULL) {
            return;
        }

        ListNode* preMiddle = findPreMiddle(head);
        ListNode* right = preMiddle->next;
        preMiddle->next = NULL;
        right = reverse(right);
        mergeToLeft(head, right);
    }

    ListNode* findPreMiddle(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head->next;
        while (fast != NULL && fast->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }

    ListNode* reverse(ListNode* head) {
        ListNode* prev = NULL;
        while (head != NULL) {
            ListNode* temp = head->next;
            head->next = prev;
            prev =head;
            head = temp;
        }
        return prev;
    }

    void mergeToLeft(ListNode* left, ListNode* right) {
        ListNode* curLeft;
        ListNode* curRight;
        while (left && right) {
            curLeft = left;
            left = left->next;
            curRight = right;
            right = right->next;
            curLeft->next = curRight;
            curRight->next = left;
        }
    }
};

Java

lang: java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {

        if (head == null || head.next == null) return;

        // Merge + reverse
        ListNode middle = findMiddle(head);
        ListNode right = middle.next;
        middle.next = null; // break at the middle
        right = reverse(right);
        mergeToLeft(head, right);
        return;        
    }


    private ListNode findMiddle(ListNode head) {

        ListNode slow = head, fast = head.next;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;        
    }

    private void mergeToLeft(ListNode left, ListNode right) {
        while (left != null && right != null) {
            ListNode leftNext = left.next;
            ListNode rightNext = right.next;
            left.next = right;
            right.next = leftNext;
            left = leftNext;
            right = rightNext;
        }
    }


    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }

        return prev;
    }
}