给定一个单链表的头部节点 head,链表长度为 N,如果 N 是偶数,那么前 N / 2 个节点算作左半区,后 N / 2 个节点算作右半区;如果 N 为奇数,那么前 N / 2 个节点算作左半区,后 N / 2 + 1个节点算作右半区。左半区从左到右依次记为 L1->L2->...,右半区从左到右依次记为 R1->R2->...,请将单链表调整成 L1->R1->L2->R2->... 的形式。
单链表的头节点 head。
在给定的函数内返回链表的头指针。
6 1 2 3 4 5 6
1 4 2 5 3 6
保证链表的长度不大于1000000
class Node { int val; Node next; Node(int val) { this.val = val; } } /* private static Node input(Scanner sc, int n) { Node head = null, p = null; while(n-- > 0) { if (head == null) { head = p = new Node(sc.nextInt()); } else { p.next = new Node(sc.nextInt()); p = p.next; } } return head; } private static void output(Node head) { Node p = head; StringBuilder cache = new StringBuilder(); while(p != null) { cache.append(p.val).append(" "); p = p.next; } if (cache.length() > 0) { cache.deleteCharAt(cache.length() - 1); } System.out.println(cache); } */
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); Node head = input(sc, n); head = merge(head); output(head); } static Node merge(Node head) { if (head == null || head.next == null) return head; Node fast = head, slow = head; Node pre = null; while(fast != null) { fast = fast.next; if (fast != null) { fast = fast.next; pre = slow; slow = slow.next; } } if (pre != null) { pre.next = null; } Node p = head, q = slow, next = null; while(p != null) { pre = q; next = q.next; q.next = p.next; p.next = q; p = q.next; q = next; } pre.next = q; return head; } private static Node input(Scanner sc, int n) { Node head = null, p = null; while(n-- > 0) { if (head == null) { head = p = new Node(sc.nextInt()); } else { p.next = new Node(sc.nextInt()); p = p.next; } } return head; } private static void output(Node head) { Node p = head; StringBuilder cache = new StringBuilder(); while(p != null) { cache.append(p.val).append(" "); p = p.next; } if (cache.length() > 0) { cache.deleteCharAt(cache.length() - 1); } System.out.println(cache); } }