日志
Reorder List (Linked List)
|
题目：
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) return;
ListNode pointerAhead = head;
ListNode pointerAfter = head;
ArrayList<ListNode> leftNodes = new ArrayList<ListNode>();
ArrayList<ListNode> rightNodes = new ArrayList<ListNode>();
leftNodes.add(head);
while (pointerAhead.next != null && pointerAhead.next.next != null) {
pointerAhead = pointerAhead.next.next;
pointerAfter = pointerAfter.next;
leftNodes.add(new ListNode(pointerAfter.val));
}
while (pointerAfter.next != null) {
pointerAfter = pointerAfter.next;
rightNodes.add(new ListNode(pointerAfter.val));
}
ListNode dummyHead = new ListNode(0);
ListNode pointer = dummyHead;
while (rightNodes.size() != 0) {
pointer.next = leftNodes.remove(0);
pointer = pointer.next;
pointer.next = rightNodes.remove(rightNodes.size()-1);
pointer = pointer.next;
}
if (leftNodes.size() == 1) pointer.next = leftNodes.remove(0);
return;
}
