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

Posted by: lexigrey on: November 3, 2013

• In: leetcode
• Leave a Comment

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: list