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}.
the idea is to break the list into two by middle reverse the second linklist, then merge them together.
public void reorderList(ListNode head) {
if (head==null||head.next==null||head.next.next==null) {
return;
}
ListNode slow = head;
ListNode fast = head;
while (slow.next!=null&&fast!=null&&fast.next!=null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode right = slow.next;
slow.next = null;
right = reverse(right);
merge(head, right);
}
public ListNode merge(ListNode l1, ListNode l2) {
ListNode newHead = l1;
while (l1!=null&&l2!=null) {
ListNode l1Next = l1.next;
ListNode l2Next = l2.next;
l1.next = l2;
l2.next = l1Next;
l1 = l1Next;
l2 = l2Next;
}
return newHead;
}
public ListNode reverse(ListNode l2) {
ListNode previous = new ListNode(0);
previous.next = l2;
ListNode last = l2;
ListNode current = last.next;
while(current!=null) {
last.next = current.next;
current.next = previous.next;
previous.next = current;
current = last.next;
}
return previous.next;
}