1 public class ReorderSingleList {
2 /**
3 * Definition for singly-linked list. class ListNode { int val; ListNode
4 * next; ListNode(int x) { val = x; next = null; } }
5 */
6 public void reorderList(ListNode head) {
7 if (head == null || (head.next == null)) {
8 return;
9 }
10 // fast and slow point find the mid position.
11 ListNode fast = head;
12 ListNode slow = head;
13 while ((fast != null) && (fast.next != null)) {
14 fast = fast.next.next;
15 slow = slow.next;
16 }
17
18 // reverse the last second list.
19 ListNode headnode = new ListNode(-1);
20 headnode.next = slow;
21 ListNode temp = headnode.next;
22 while (temp.next != null) {
23 ListNode insert = temp.next;
24 ListNode currNext = insert.next;
25 insert.next = headnode.next;
26 headnode.next = insert;
27 temp.next = currNext;
28 }
29
30 // merge insert
31 ListNode firstcur = head;
32 ListNode secOndcur= headnode.next;
33 while (firstcur != slow && (secondcur != slow)) {// at first,I make a mistake in here;
34 ListNode firstnex = firstcur.next;
35 ListNode secOndnex= secondcur.next;
36 firstcur.next = secondcur;
37 secondcur.next = firstnex;
38 firstcur = firstnex;
39 secOndcur= secondnex;
40 }
41 }
42
43 public static void main(String[] args) {
44 ListNode t5 = new ListNode(5);
45 ListNode t4 = new ListNode(4, t5);
46 ListNode t3 = new ListNode(3, t4);
47 ListNode t2 = new ListNode(2, t3);
48 ListNode t1 = new ListNode(1, t2);
49 new ReorderSingleList().reorderList(t1);
50 System.out.println(t1);
51 }
52
53 }