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}
.A:
就是简单的,递归调用,每次减少2步,然后,把最后一个弄到前面来。
---------------------------可是,当list太长的时候,有run time error???????? 这里,估计是StackOverflowError
调用得太多太长。因此,我们下一步就考虑用循环而不是递归????
public class ReorderList { public void reorderList(ListNode head) { // use re-cursive call, to update // find number of Nodes int nNodes = 0; ListNode pointer = head; while (pointer != null) { nNodes++; pointer = pointer.next; } if (nNodes > 2) { reorderList(head, nNodes); } } private ListNode reorderList(ListNode head, int nNodes) { // return the LastNode of reordered list if (nNodes == 1) { return head; } else if (nNodes == 2) { return head.next; } else { // nNodes > 2 ListNode lastOfSub = reorderList(head.next, nNodes - 2); // detatch the last node ListNode lastNode = lastOfSub.next; lastOfSub.next = lastNode.next; // insert last node afte head lastNode.next = head.next; head.next = lastNode; return lastOfSub; } } }------------------------------下面的算法,避免了stack over flow error---------------
思想是:既然就是把后半儿插入到前半部分。那么我们只需要取下后半部分,然后把指针逆转,再加入,即可。
public class Solution { public void reorderList(ListNode head) { // IDEA: we need detach the right half part, and reverse their list if (head == null) { return; } // find the middle ListNode header1 = new ListNode(0); header1.next = head; ListNode slow = header1, fast = header1; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; } ListNode midNode = slow.next; slow.next = null; // reverse the list pointer ListNode header2 = new ListNode(0); // HEADER only ListNode tmp; while (midNode != null) { tmp = midNode; midNode = midNode.next; tmp.next = header2.next; header2.next = tmp; } // Now add the reversed right half to left half list ListNode p1 = header1.next; while (header2.next != null) { // detach the first of tmp = header2.next; header2.next = tmp.next; // insert the detached node after p1 tmp.next = p1.next; p1.next = tmp; p1 = tmp.next; } } }
Mistakes:
1: 方法一,用了O(n) 次调用,效率比较差。
2: 方法2 的时候,开始忘了 加入:
header2.next = tmp.next;
Learned:
No comments:
Post a Comment