143. Reorder List

Leetcode Linked List

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

You may not modify the values in the list's nodes, only nodes itself may be changed.

Example 1:

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

Example 2:

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

分析

/**
 * Given a singly linked list L: L0 → L1 → … → Ln-1 → Ln,
 * reorder it to: L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
 *
 * You may not modify the values in the list's nodes,
 * only nodes itself may be changed.
 *
 *
 * Example:
 * Given 1->2->3->4, reorder it to 1->4->2->3.
 * Given 1->2->3->4->5, reorder it to 1->5->2->4->3.
 *
 * https://leetcode.com/problems/reorder-list/description/
 *
 * 由于后半部分链表需要倒置，所以很显然能直接想到使用stack，
 * 所以分成三部分：
 * 1. 找到中点和终点
 * 2. 把中点-终点部分放入stack中
 * 3. 依次从链表和stack中取出元素，链接起来
 *
 *
 *
 */
public class Q143ReorderList {

    public static void reorderList(ListNode head) {

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

        ListNode mid = head, tail = head.next;
        boolean odd = false;

        while ((tail != null) && ( tail.next != null)) {
            mid = mid.next;
            tail = tail.next.next;
        }

        // 判断链表个数奇偶
        if (tail == null) {
            odd = true;
        }

        Stack<ListNode> stack = new Stack<>();

        mid = mid.next;
        while (mid != tail) {
            stack.push(mid);
            mid = mid.next;
        }

        if (!odd) {
            stack.push(mid);
        }


        ListNode res = new ListNode(0), pos = head;
        ListNode tmp = res, tmp2;
        int size = stack.size();
        for (int i = 0; i < size ; i++) {
            tmp2 = pos.next; // store pos next elem
            res.next = pos;
            res.next.next = stack.pop();
            res = res.next.next;
            pos = tmp2; // resotre pos next elem
        }

        if (odd) {
            res.next = pos;
            res = res.next;
        }
        res.next = null;

        head = tmp;
    }
}