题解：找分割点、切割、逆序、重组
重排链表
http://www.nowcoder.com/questionTerminal/3d281dc0b3704347846a110bf561ef6b
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public void reorderList(ListNode head) {
ListNode nhead = head;
int cnt = 0;
while(nhead != null) {
cnt ++;
nhead = nhead.next;
}
if(cnt == 0) {
return;
}
cnt = (cnt+1) / 2;
nhead = head;
for(int i = 0;i < cnt - 1; i ++ ){
nhead = nhead.next;
}
ListNode next = nhead.next;
while(next != null && next.next != null) {
ListNode nn = next.next;
next.next = nn.next;
nn.next = nhead.next;
nhead.next = nn;
}
ListNode p1 = head;
ListNode p2 = nhead.next;
nhead.next = null;
if(p2 == null) {
return;
}
while(p1.next != null && p2.next != null) {
next = p2.next;
p2.next = p1.next;
p1.next = p2;
p1 = p1.next.next;
p2 = next;
}
p2.next = p1.next;
p1.next = p2;
}
} 
腾讯成长空间 5881人发布
