Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
You must do this in-place without altering the nodes' values.
For example, Given {1,2,3,4}, reorder it to {1,4,2,3}.
就是一道快慢指针加上反转链表的题，仔细点就好。
写的有点啰嗦，还需要进一步优化下，里边的变量有点多。
代码：
public void reorderList(ListNode head) { if(head == null || head.next == null) return; ListNode slow = head; ListNode fast = head; while(fast.next != null && fast.next.next != null){ fast = fast.next.next; slow = slow.next; } //reverse 2nd half ListNode p2 = reverse(slow.next); slow.next = null; ListNode p1 = head; ListNode dummy = new ListNode(-1); dummy.next = head; ListNode p = dummy; while(p1 != null && p2 != null){ p.next = p1; ListNode temp1 = p1.next; ListNode temp2 = p2.next; p.next.next = p2; p = p.next.next; p1 = temp1; p2 = temp2; } if(p1 != null){ p.next = p1; } } private ListNode reverse(ListNode slow){ ListNode dummy = new ListNode(-1); dummy.next = slow; ListNode pre = dummy; ListNode cur = slow; while(cur != null){ ListNode temp = cur.next; cur.next = pre; pre = cur; cur = temp; } slow.next = null; return pre; }
