1+ /*
2+ Author: King, wangjingui@outlook.com
3+ Date: Jan 8, 2015
4+ Problem: Reorder List
5+ Difficulty: Easy
6+ Source: http://oj.leetcode.com/problems/reorder-list/
7+ Notes:
8+ Given a singly linked list L: L0->L1->...->Ln-1->Ln,
9+ reorder it to: L0->Ln->L1->Ln-1->L2->Ln-2->...
10+ You must do this in-place without altering the nodes' values.
11+ For example,
12+ Given {1,2,3,4}, reorder it to {1,4,2,3}.
13+
14+ Solution: Reverse the back half first, then reorder.
15+ */
16+
17+
18+ /**
19+ * Definition for singly-linked list.
20+ * class ListNode {
21+ * int val;
22+ * ListNode next;
23+ * ListNode(int x) {
24+ * val = x;
25+ * next = null;
26+ * }
27+ * }
28+ */
29+ public class Solution {
30+ public void reorderList_1 (ListNode head ) {
31+ ListNode slow =head ,fast =head ;
32+ if (head ==null ||head .next ==null )return ;
33+ while (fast .next !=null &&fast .next .next !=null ) {
34+ fast =fast .next .next ;
35+ slow =slow .next ;
36+ }
37+ fast =slow .next ;
38+ slow .next =null ;
39+ slow =head ;
40+ ListNode pre =null ;
41+ while (fast !=null ) {
42+ ListNode next =fast .next ;
43+ fast .next =pre ;
44+ pre =fast ;
45+ fast =next ;
46+ }
47+ fast =pre ;
48+ while (fast !=null ) {
49+ ListNode fastnext =fast .next ;
50+ fast .next =slow .next ;
51+ slow .next =fast ;
52+ fast =fastnext ;
53+ slow =slow .next .next ;
54+ }
55+ }
56+ public void reorderList_2 (ListNode head ) {
57+ ListNode slow =head ,fast =head ;
58+ if (head ==null ||head .next ==null )return ;
59+ while (fast .next !=null &&fast .next .next !=null ) {
60+ fast =fast .next .next ;
61+ slow =slow .next ;
62+ }
63+ fast =slow .next ;
64+ while (fast .next !=null ) {
65+ ListNode move =fast .next ;
66+ fast .next =move .next ;
67+ move .next =slow .next ;
68+ slow .next =move ;
69+ }
70+ fast =slow .next ;
71+ slow .next =null ;
72+ slow =head ;
73+ while (fast !=null ) {
74+ ListNode fastnext =fast .next ;
75+ fast .next =slow .next ;
76+ slow .next =fast ;
77+ fast =fastnext ;
78+ slow =slow .next .next ;
79+ }
80+ }
81+ }
