算法_链表_重排链表

/**
 * ///TODO ---sjn---重写---
 * 给定一个单链表 L 的头节点 head ，单链表 L 表示为：
 * L0 → L1 → … → Ln - 1 → Ln
 * 请将其重新排列后变为：
 * L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
 * 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 * 示例 1：
 * 输入：head = [1,2,3,4]
 * 输出：[1,4,2,3]
 * 示例 2：
 * 输入：head = [1,2,3,4,5]
 * 输出：[1,5,2,4,3]
 * 提示：
 * 链表的长度范围为 [1, 5 * 104]
 * 1 <= node.val <= 1000
 */
public class 重排链表 {
    /**
     * 方法一：利用栈进行链表合并，附加条件是【这个链表必须是有序的】
     */
    public static void reorderList(Node.IntNode head) {
        //node入栈
        Stack<Node.IntNode> stackNodes = new Stack<>();
        Node.IntNode tempNode = head;
        int count = 0;
        while (tempNode != null) {
            count++;
            stackNodes.push(tempNode);
            tempNode = tempNode.next;
        }

        //循环合并
        Node.IntNode currNode = head;
        while (currNode != null) {
            Node.IntNode currNextNode = currNode.next;
            Node.IntNode tempPopNode = stackNodes.pop();
            if (currNode.val < tempPopNode.val) {//当链表有序递增的场景利用大小进行判断
                currNode.next = tempPopNode;//进行节点的插入
                tempPopNode.next = currNextNode;
            } else {
                //判断currNode节点后是否还有一个数，当为偶数的时候有
                if (count > 1 && count / 2 == 0) {//偶数
                    currNode.next.next = null;
                } else {//奇数个
                    currNode.next = null;
                }
                break;
            }
            currNode = currNextNode;
        }
    }

    /**
     * 方法二：链表分割，翻转第二个链表，合并
     * 1 -> 2 -> 3 -> 4 -> 5 -> 6
     * 第一步，将链表平均分成两半
     * 1 -> 2 -> 3
     * 4 -> 5 -> 6
     * 第二步，将第二个链表逆序
     * 1 -> 2 -> 3
     * 6 -> 5 -> 4
     * 第三步，依次连接两个链表
     * 1 -> 6 -> 2 -> 5 -> 3 -> 4
     */
    public static void reorderList2(Node.IntNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return;
        }
        //找中点，链表分成两个
        Node.IntNode slow = head;
        Node.IntNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        Node.IntNode newHead = slow.next;
        slow.next = null;
        //第二个链表倒置
        newHead = reverseList(newHead);
        //链表节点依次连接
        while (newHead != null) {
            Node.IntNode temp = newHead.next;
            newHead.next = head.next;
            head.next = newHead;
            head = newHead.next;
            newHead = temp;
        }
    }

    private static Node.IntNode reverseList(Node.IntNode head) {
        if (head == null) {
            return null;
        }
        Node.IntNode tail = head;
        head = head.next;

        tail.next = null;

        while (head != null) {
            Node.IntNode temp = head.next;
            head.next = tail;
            tail = head;
            head = temp;
        }

        return tail;
    }

    /**
     * 方法三：ArrayList双向遍历
     */
    public static void reorderList3(Node.IntNode head) {
        if (head == null) {
            return;
        }
        //存到 list 中去
        List<Node.IntNode> list = new ArrayList<>();
        while (head != null) {
            list.add(head);
            head = head.next;
        }
        //头尾指针依次取元素
        int i = 0, j = list.size() - 1;
        while (i < j) {
            list.get(i).next = list.get(j);
            i++;
            //偶数个节点的情况，会提前相遇
            if (i == j) {
                break;
            }
            list.get(j).next = list.get(i);
            j--;
        }
        list.get(i).next = null;
    }

    public static void main(String[] args) {
        Node.IntNode resNode = Node.getIncrNode(9);
        reorderList3(resNode);
        Node.IntNode.printNodes(resNode);
    }
}