@Test(timeout = 3000) public void testShuffle() { Random r = new Random(); for (int n = 2; n <= 20; n ++) { System.out.println("test "+n); int N = 100000; int[][] check = new int[n][n]; for (int i = 0; i < N; i++) { Node cur = linkedList.buildLinkedList(n); cur = linkedList.shuffle(cur); int[] res = new int[n]; for (int j = 0; j < n; j++, cur = cur.next) { res[cur.val]++; check[j][cur.val]++; } int[] expect = new int[n]; Arrays.fill(expect, 1); Assert.assertArrayEquals(expect, res); } double expect = N / n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { Assert.assertTrue(Math.abs(expect - check[i][j]) <= 0.06 * expect); } } } }
public Node shuffle(Node list) { if (list == null || list.next == null) return list; Node slow = list, fast = list.next; int preL = 1; while (fast != null && fast.next != null) { slow = slow.next; preL++; fast = fast.next.next; } int postL = preL; if (fast == null) { postL--; } Node post = slow.next, pre = list; slow.next = null; return merge(shuffle(pre),preL,shuffle(post),postL); }
ShuffleLinkedList { public Node shuffle(Node list) { if (list == null || list.next == null) return list; Node slow = list, fast = list.next; int preL = 1; while (fast != null && fast.next != null) { slow = slow.next; preL++; fast = fast.next.next; } int postL = preL; if (fast == null) { postL--; } Node post = slow.next, pre = list; slow.next = null; return merge(shuffle(pre),preL,shuffle(post),postL); } }
ShuffleLinkedList { public Node shuffle(Node list) { if (list == null || list.next == null) return list; Node slow = list, fast = list.next; int preL = 1; while (fast != null && fast.next != null) { slow = slow.next; preL++; fast = fast.next.next; } int postL = preL; if (fast == null) { postL--; } Node post = slow.next, pre = list; slow.next = null; return merge(shuffle(pre),preL,shuffle(post),postL); }  }
ShuffleLinkedList { public Node shuffle(Node list) { if (list == null || list.next == null) return list; Node slow = list, fast = list.next; int preL = 1; while (fast != null && fast.next != null) { slow = slow.next; preL++; fast = fast.next.next; } int postL = preL; if (fast == null) { postL--; } Node post = slow.next, pre = list; slow.next = null; return merge(shuffle(pre),preL,shuffle(post),postL); }  Node buildLinkedList(int n); Node shuffle(Node list); }
ShuffleLinkedList { public Node shuffle(Node list) { if (list == null || list.next == null) return list; Node slow = list, fast = list.next; int preL = 1; while (fast != null && fast.next != null) { slow = slow.next; preL++; fast = fast.next.next; } int postL = preL; if (fast == null) { postL--; } Node post = slow.next, pre = list; slow.next = null; return merge(shuffle(pre),preL,shuffle(post),postL); }  Node buildLinkedList(int n); Node shuffle(Node list);  }