链表排序 - Githubissues

使用MergeSort的in-place做法：


static ListNode sort(ListNode root) {

    if (root == null) return null;

    if (root.next == null) {
        return root;
    }

    // find the middle node by two pointers with 1x and 2x step
    ListNode p1 = root; // pointer with 1x step
    ListNode p2 = root.next; // pointer with 2x step

    while (p2 != null && p2.next != null) {
        p1 = p1.next;
        p2 = p2.next.next;
    }

    ListNode l1 = root;
    ListNode l2 = p1.next;
    p1.next = null; // split to two linked lists;

    return merge( sort(l1), sort(l2) );
}

static ListNode merge(ListNode l1, ListNode l2) {

    ListNode root = l1.val <= l2.val ? l1 : l2; // pick the root first

    ListNode p1 = null; // point to previous, init with null
    ListNode n2 = l2.next; // point to next

    while (l2 != null ) {

        // l2 is bigger than anyone in l1, put l2 to the end, and break the loop
        if (l1 == null) {
            p1.next = l2;
            break;
        }

        // if find l2 smaller than l1, put l2 before l1.
        if (l2.val < l1.val) {
            n2 = l2.next;
            l2.next = l1;
            if (p1 != null) {
                p1.next = l2;
            }
            p1 = l2;
            l2 = n2;
        }
        // if find l2 bigger than l1, compare next l1;
        else {
            p1 = l1;
            l1 = l1.next;
        }
    }

    return root;
}

public static void main(String [] args) {
    ListNode l1 = new ListNode();
    l1.val = 1;
    ListNode l2 = new ListNode();
    l2.val = 1;
    ListNode l3 = new ListNode();
    l3.val = 1;
    ListNode l4 = new ListNode();
    l4.val = 1;
    ListNode l5 = new ListNode();
    l5.val = 1;
    ListNode l6 = new ListNode();
    l6.val = 6;

    l1.next = l2;
    l2.next = l3;
    l3.next = l4;
    l4.next = l5;
    l5.next = l6;

    pr(l1);
    ListNode root = sort(l1);
    pr(root);
}

static void pr(ListNode t) {
    while(t != null) {
        System.out.println(t);
        t = t.next;
    }
}

public static class ListNode {
    public int val;
    public ListNode next;
}

关于链表题：

这个程序的思路不复杂，使用两个pointer找到中间的位置，然后分成两段分别进行递归sort后，merge到一起。但写这个程序的时候我用了很长时间，写完之后编译也出现了各种NullPointer的错误。

花了很长时间的原因主要在做链表的思路不清楚，链表跟递归一样，只考虑当前递归（节点），没有全局的状态。所以，碰到这种题 _第一件事情_ 就考虑正常情况下中间情况，让主逻辑能跑通，然后递归终止的条件以及边界的特殊情况。比如上面代码中merge方法片段的：

    while (l2 != null ) {

        // l2 is bigger than anyone in l1, put l2 to the end, and break the loop
        if (l1 == null) {
            p1.next = l2;
            break;
        }

        // if find l2 smaller than l1, put l2 before l1.
        if (l2.val < l1.val) {
            n2 = l2.next;
            l2.next = l1;
            if (p1 != null) {
                p1.next = l2;
            }
            p1 = l2;
            l2 = n2;
        }
        // if find l2 bigger than l1, compare next n1;
        else {
            p1 = l1;
            l1 = l1.next;
        }
    }

最开始考虑应该其中的主逻辑，其他的是后来一步步加上的：

    while (l2 != null ) {

        // l2 is bigger than anyone in l1, put l2 to the end, and break the loop
        //if (l1 == null) {
        //  p1.next = l2;
        //  break;
        //}

        // if find l2 smaller than l1, put l2 before l1.
        if (l2.val < l1.val) {
            n2 = l2.next;
            l2.next = l1;
            //if (p1 != null) {
                p1.next = l2;
            //}
            p1 = l2;
            l2 = n2;
        }
        // if find l2 bigger than l1, compare next l1;
        else {
            p1 = l1;
            l1 = l1.next;
        }
    }

另外，NullPointer经常出现的原因是链表遍历到了尽头之后仍然继续遍历，就导致了null.next的错误，所以最好在写while循环的判断条件时仔细斟酌，把链表靠近结尾的可能出现的几种情况都理清楚，避免碰到null.next。

GingerBear / IS-Job-Hunting

链表排序 #15

关于链表题：