Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
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
Given
{1,2,3,4}
, reorder it to {1,4,2,3}
ListNode slow, fast;
slow=head;
fast=head;
// find middle of linked list
while(slow != null && fast != null && fast.next !=null) {
slow = slow.next;
fast = fast.next.next;
}
// reverse second half of list and divide into two list
ListNode secondHead = null;
if(slow != null) {
secondHead = reverse(slow.next);
slow.next = null;
}
// join two lists with reoder
slow = head;
while(secondHead != null) {
ListNode temp = slow.next;
slow.next = secondHead;
ListNode temp2 = secondHead.next;
secondHead.next = temp;
slow = temp;
secondHead = temp2;
}
}
private ListNode reverse(ListNode L) {
ListNode prev = null;
ListNode cur = L;
while (cur != null) {
ListNode next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
return prev;
}
No comments:
Post a Comment