首页 > ACM题库 > LeetCode > Reorder List(链表重排序)-LeetCode
2014
08-23

Reorder List(链表重排序)-LeetCode

Reorder List

Given a singly linked list LL0→L1→…→Ln-1→Ln,
reorder it to: L0→LnL1→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}.

题目链接:https://oj.leetcode.com/problems/reorder-list/

题目不难,按照规则对链表重新排序即可。我的思路如下:

1) 用快慢指针找到中间节点,将链表分成两部分。

2) 对后面一半的链表逆序,这个也是常见的问题了(链表反转)。

3) 合并两个链表。

此题很适合作为面试题目,现场纸上写代码要做到一气呵成。

public class Solution {
    public void reorderList(ListNode head) {
        if(head == null || head.next == null) return;

        ListNode slow = head;
        ListNode fast = head;
        while(fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode mid = slow.next;
        ListNode last = mid;
        ListNode pre = null;
        while(last != null){
            ListNode next = last.next;
            last.next = pre;
            pre = last;
            last = next;
        }
        slow.next = null;

        while(head != null && pre != null){
            ListNode next1 = head.next;
            head.next = pre;
            pre = pre.next;
            head.next.next = next1;
            head = next1;
        }
    }
}

  1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

  2. 漂亮。佩服。
    P.S. unsigned 应该去掉。换行符是n 不是/n
    还可以稍微优化一下,
    int main() {
    int m,n,ai,aj,bi,bj,ak,bk;
    while (scanf("%d%d",&m,&n)!=EOF) {
    ai = sqrt(m-1);
    bi = sqrt(n-1);
    aj = (m-ai*ai-1)>>1;
    bj = (n-bi*bi-1)>>1;
    ak = ((ai+1)*(ai+1)-m)>>1;
    bk = ((bi+1)*(bi+1)-n)>>1;
    printf("%dn",abs(ai-bi)+abs(aj-bj)+abs(ak-bk));
    }
    }