无序链表排序_双向链表排序算法

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

需求

给定一个无序的链表，输出有序的链表。

分析

链表排序比较特殊，由于不连续的性质，所以在进行排序的时候要引入外排思想，因此归并排序或者多路归并就成为了排序的选择。
归并排序分为拆分、合并两个阶段：
1. 拆分
需要找出链表中间节点，并根据中间节点拆分成两个独立的链表，递归直到拆分成单个节点为止。
2. 合并
由于此时每个链表都为单节点，所以对于拆分的两个子链表实质上是有序链表合并问题。

代码

下面是示例代码

    private class Node {
        int value;
        Node next;
    }

    private Node getRandomList(int length)
    {
        Node node = new Node();
        int randomNum = (int) ((Math.random() * 100) % 100);
        node.value = randomNum;
        Node head = node;
        for(int i = 0; i < length; i++)
        {
            randomNum = (int) ((Math.random() * 100) % 100);
            Node temp = new Node();
            temp.value = randomNum;
            node.next = temp;
            node = temp;
        }

        return head;
    }

    private Node getMiddleNode(Node head)
    {
        Node index1 = head;
        Node index2 = head;
        while(index2.next != null && index2.next.next != null)
        {
            index1 = index1.next;
            index2 = index2.next.next;
        }

        return index1;
    }

    private Node mergeSort(Node head)
    {
        if(head.next == null)
            return head;

        Node middelNode = getMiddleNode(head);
        Node head1 = head;
        Node head2 = middelNode.next;
        middelNode.next = null;

        head1 = mergeSort(head1);
        head2 = mergeSort(head2);

        Node currenthead = mergeSequentialList(head1, head2);

        return currenthead;
    }

    private Node mergeSequentialList(Node head1, Node head2)
    {

        if(head1 == null)
            return head2;
        if(head2 == null)
            return head1;
        Node currentNode = null;
        if(head1.value < head2.value)
        {
            head1.next = mergeSequentialList(head1.next, head2);
            currentNode = head1;
        }
        else
        {
            head2.next = mergeSequentialList(head1, head2.next);
            currentNode = head2;
        }

        return currentNode;
    }

    private int outputListValue(Node list, StringBuffer bf) {
        // TODO Auto-generated method stub

        int i = 0;
        while(list.next != null)
        {
            bf.append(list.value + "-");
            i++;
            list = list.next;
        }
        return i;
    }


    public void main()
    {
        Node list = getRandomList(50);
        list = mergeSort(list);
        StringBuffer bf = new StringBuffer();
        int count = outputListValue(list, bf);
        String result = bf.toString();  
    }

复杂度

对于中间节点的查找，可以使用两指针不同步调方式，查找的时间复杂度为O(n)。
对于两个有序子链表合并，递归深度为最短链表深度，时间复杂度为O(n)。
由于归并排序会调用logn次，所以最终的时间复杂度为(2n)logn = O(nlogn)。

总结

无序链表排序考察的知识点比较多，首先要深刻理解归并排序的思想与应用场景，其次算法中也运用到了链表中间节点查找、两个有序链表归并等单算法，并且也要考虑单算法其中的细节。整体算法难度比较难。