[数据结构与算法]第二章 链表问题（按照左右半区的方式重新组合单链表）

【题目】

????????给定一个单链表的头部节点head，链表长度为N。 如果N为偶数，那么前N/2个节点算作左半区，后N/2个节点算作右半区； 如果N为奇数，那么前N/2个节点算作左半区，后N/2+1个节点算作右半区； 左半区从左到右依次记为L1->L2->...，右半区从左到右依次记为R1->R2->...。请将单链表调整成L1->R1->L2->R2->...的样子。 例如： 1->2->3->4 调整后：1->3->2->4 1->2->3->4->5 调整后：1->3->2->4->5 要求：如果链表长度为N，时间复杂度请达到O(N)，额外空间复杂度请达到O(1)。

【解答】

package zcy;

public class P90_RecombNode {

    public static void main(String[] args) {

        Node node = new Node(1);
        node.next = new Node(2);
        node.next.next = new Node(3);
        node.next.next.next = new Node(4);
        node.next.next.next.next = new Node(5);
        node.next.next.next.next.next = new Node(6);
        node.next.next.next.next.next.next = new Node(7);
        node.next.next.next.next.next.next.next = new Node(8);

        Node node1 = recombNode(node);
        while (node1 != null) {
            System.out.println(node1.value);
            node1 = node1.next;
        }

    }

    /*
    1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8

    1 -> 2 -> 3 -> 4 -> null
    5 -> 6 -> 7 -> 8 -> null

    1 -> 5 -> 2 -> 3 -> 4 -> null
    6 -> 7 -> 8 -> null

    1 -> 5 -> 2 -> 6 -> 3 -> 4 -> null
    7 -> 8 -> null

    1 -> 5 -> 2 -> 6 -> 3 -> 7 -> 4 -> null
    8 -> null

    1 -> 5 -> 2 -> 6 -> 3 -> 7 -> 4 -> 8 -> null
    */
    public static Node recombNode(Node node) {

        if (node == null || node.next == null || node.next.next == null) {
            return node;
        }
        Node left = node;
        Node right = node.next;
        while (right.next != null && right.next.next != null) {
            left = left.next;
            right = right.next.next;
        }
        right = left.next;
        left.next = null;
        left = node;
        Node cur = null;
        while (left.next != null) {
            cur = right.next;
            right.next = left.next;
            left.next = right;
            left = left.next.next;
            right = cur;
        }
        left.next = right;
        return node;
    }

    public static class Node {

        public int value;

        public P90_RecombNode.Node next;

        public Node(int value) {
            this.value = value;
        }
    }

}