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 || head.next.next == null)) { int len = 0; ListNode cur = head; while(cur != null) { len++; cur = cur.next; } //System.out.println("len:" + len); int half = (len + 1) / 2; cur = head; ListNode second = head.next; for (int i = 1; i < half; i++) { cur = second; second = second.next; } cur.next = null; ListNode secondHead; cur = second.next; secondHead = second; secondHead.next = null; while (cur != null) { ListNode temp = cur; cur = cur.next; temp.next = secondHead; secondHead = temp; } ListNode cur1 = head; ListNode cur2 = secondHead; while(cur2 != null) { ListNode next1 = cur1.next; ListNode next2 = cur2.next; cur2.next = cur1.next; cur1.next = cur2; cur1 = next1; cur2 = next2; } } }