-
Notifications
You must be signed in to change notification settings - Fork 0
/
143.java
47 lines (46 loc) · 1.17 KB
/
143.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
ListNode reverse(ListNode head) {
ListNode pre = null;
ListNode cur = head;
ListNode next = cur.next;
while(cur != null) {
cur.next = pre;
pre = cur;
cur = next;
if(next != null) next = next.next;
}
return pre;
}
public void reorderList(ListNode head) {
if(head == null || head.next == null ) return ;
// separate list to two parts
ListNode pre = null;
ListNode slow = head;
ListNode fast = head;
while(fast!= null && fast.next !=null) {
fast = fast.next.next;
pre = slow;
slow = slow.next;
}
pre.next = null;
slow = reverse(slow);
pre = head;
while(pre != null) {
ListNode pn = pre.next;
ListNode sn = slow.next;
pre.next = slow;
if(pn != null)
slow.next = pn;
pre = pn;
slow = sn;
}
}
}