【题目】
给定一个单链表的头部节点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 -> 81 -> 2 -> 3 -> 4 -> null5 -> 6 -> 7 -> 8 -> null1 -> 5 -> 2 -> 3 -> 4 -> null6 -> 7 -> 8 -> null1 -> 5 -> 2 -> 6 -> 3 -> 4 -> null7 -> 8 -> null1 -> 5 -> 2 -> 6 -> 3 -> 7 -> 4 -> null8 -> null1 -> 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;}}}