Given a singly linked list L: L0→L1→…→Ln-1→Ln,reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
You may not modify the values in the list's nodes, only nodes itself may be changed.
思路：
1. find mid
2. cut list
3. reverse slow part
4. merge two parts
代码：
1 class Solution { 2 public void reorderList(ListNode head) { 3 // corner case 4 if(head == null || head.next == null) return; 5 // init 6 ListNode fast = head; 7 ListNode slow = head; 8 ListNode prev = null; 9 // find mid 10 while(fast != null && fast.next != null){ 11 prev = slow; 12 slow = slow.next; 13 fast = fast.next.next; 14 } 15 //cut list 16 prev.next = null; 17 //recurse slow part 18 slow = reverse(slow); 19 fast = head; 20 // merge two parts 21 while(fast.next!=null){ 22 ListNode temp = fast.next; 23 fast.next = slow; 24 slow = slow.next; 25 fast.next.next = temp; 26 fast = temp; 27 } 28 fast.next = slow; 29 } 30 31 private ListNode reverse(ListNode head){ 32 ListNode cur = head; 33 ListNode pre = null; 34 while(cur != null){ 35 ListNode temp = cur.next; 36 cur.next = pre; 37 pre=cur; 38 cur=temp; 39 } 40 return pre; 41 } 42 }
转载于:https://www.cnblogs.com/liuliu5151/p/9808285.html
