将1->2->3->4重排为1->4->2>3
分析:这道题的思路是先快慢指针找到链表中点,将链表切分,然后将后半链表倒序,之后两个链表你一个我一个进行排序。
参考代码:
public void reorderList(ListNode head) {
ListNode slow = head,fast=head;
//找链表中点
while(fast.next!=null&&fast.next.next!=null){
fast=fast.next.next;
slow=slow.next;
}
ListNode two=slow.next;
slow.next=null;
ListNode one =head;
//后面的链表翻转
two=reverse(two);
while(two!=null){
ListNode tmp1=one.next;
ListNode tmp2=two.next;
one.next=two;
two.next=tmp1;
one=tmp1;
two=tmp2;
}
