单向链表排序

10月29日面试题

题目

一个单向链表增序排序
例如：链表6->5->7->3->1->2，排序后：1->2->3->5->6->7

解析

1. 插入排序思想：依次遍历单向链表的每一个节点，执行插入排序。初始化一个新链表的头节点newHead，每次读取一个节点后，都从newHead往后遍历，插入排序的位置上。直到所有节点完成排序，返回newHead就是新的有序链表。时间复杂度为O(n*n)。
2. 快速排序思想：在链表中取一个节点为标兵节点，其余节点与标兵节点比较，拆分为两个子链表，一个均小于等于标兵节点，一个均大于标兵节点，两个子链表继续递归逻辑。标兵节点在中间连接两个排序子链表，返回这个链接好的队列就是有序的队列。时间复杂度为O(n*lgn)。

代码

快速排序思想的代码实现

class Node{
    int v;
    Node next;
    public Node(int v){ this.v = v; }
}

private Node[] quickSort(Node h, Node t){
    Node[] result = new Node[2];
    if(null == h){
        return null;
    }
    if(h == t){
        result[0] = h; result[1] = t; return result;
    }
    //小于等于标兵节点的子链表
    Node h1 = new Node(0); Node t1 = h1;
    //大于标兵节点的子链表
    Node h2 = new Node(0); Node t2 = h2;
    //选择链表的第一个节点为标兵节点
    Node setinel = h;
    h = h.next;
    while(h != t.next){
        if(h.v <= setinel.v){
            t1.next = h;
            t1 = h;
        } else {
            t2.next = h;
            t2 = h;
        }
        h = h.next;
    }
    //子链表的尾节点的next置空
    t1.next = null; 
    t2.next = null;
    //递归对两个子链表进行排序，剔除自定义的头节点
    Node[] res1 = quickSort(h1.next, t1);
    Node[] res2 = quickSort(h2.next, t2);
    //判断排序的子链表是否为空，若为空，标兵节点就是新链表的第一个节点或最后一个节点
    if (null == res1){
        result[0] = setinel;
    } else {
        res1[1].next = setinel;
        result[0] = res1[0];
    }
    if (null == res2){
        result[1] = setinel;
    } else {
        setinel.next = res2[0];
        result[1] = res2[1];
    }
    //返回排序好链表的第一个节点和最后一个节点
    //返回最后一个节点为了方便与哨兵节点连接为一个新链表
    return result;
}