Lexi's Leetcode solutions

[leetcode] Reorder List | 单链表前后交叉

Posted on: November 3, 2013

a->b->c->d->e => a->e->b->d->c,要求inplace,不能用额外空间(要不然直接reverse成另一个就好办了),不能直接改动list的值。

这题有点写长了,过一阵看看网上有没有好点的做法。O(n)。

算法:

  1. 过一遍算出总长度len
  2. 再过一遍找到中点或第二部分的第一个点(a->b->c->d->e和a->b->c->d的都是c)
  3. reverse后半部分,变成a->b->c<-d<-e 或者 a->b->c<-d,最后中点c的next置空
  4. 两头穿插合并,直到找到c这点。c肯定是一起找到(奇数)或者右半部分先找到(偶数)
public void reorderList(ListNode head) {
    if (head == null)
        return;
    ListNode p = head;
    int len = 0;
    while (p != null) {
        len++;
        p = p.next;
    }
    p = head;
    for (int k = 0; k < len / 2; k++) {
        p = p.next;
    } //p points to mid point
    ListNode curr = p.next, next;
    p.next = null;
    while (curr != null) { //开始reverse后半部分
        next = curr.next;
        curr.next = p;
        p = curr;
        curr = next;
    }//now p points to the last ele
    ListNode h = head;
    while (h.next != p && h != p) {
        ListNode tempH = h.next;
        ListNode tempP = p.next;
        h.next = p;
        p.next = tempH;
        h = tempH;
        p = tempP;
    }
}
Tags:

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Blog Stats

  • 222,234 hits
November 2013
M T W T F S S
 123
45678910
11121314151617
18192021222324
252627282930  
%d bloggers like this: