链表排序(归并排序算法 快速排序算法)

链表排序算法和用数组排序,实现是有所不同的。

思想相同,单不能硬套数组的实现方法。

归并排序算法

时间复杂度nlogn

/**
 * Created by chris on 2014/11/19.
*归并排序,需要寻找中间的节点,像数组一样通过循环计数,判断是否到中点,时间复杂度高,代码复杂	
 */
public class MergeSortList {
    public ListNode sortList(ListNode head) {

        if (head == null || head.next == null) return head;

        ListNode p = head;
        int count = 1;
        while (p.next != null) {
            count++;
            p = p.next;
        }

        return mergeSortList(head, p, count);


    }
    public ListNode mergeSortList(ListNode left, ListNode right, int n){
        if (left != right) {

            ListNode pMid = left;
            ListNode pMidNext = left;
            int count = n;
            while (count-- != n-1 / 2){
                if (pMid != null)
                    pMid = pMid.next;
            }
            if (pMid != null) {
                pMidNext = pMid.next;
            }
            pMid.next = null;

            ListNode p1 = mergeSortList(left, pMid, n/2);
            ListNode p2 = mergeSortList(pMidNext, right, n/2);
            return mergeTwoLists(p1, p2);
        }
    return left;
    }




    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 != null && l2 != null){//因为上面用计数的的方式寻找中点,复杂度高,现在排除一个链表中最后一个元素小于另一个链表第一个元素的特殊情况
            ListNode p = l2;
            while (p.next != null){
                p = p.next;
            }
            if (p.val <= l1.val) {
                p.next = l1;
                return l2;
            }
            p = l1;
            while (p.next != null){
                p = p.next;
            }

            if (p.val <= l2.val) {
                p.next = l2;
                return l1;
            }

        }


        ListNode l = (l1 == null) ? l1 : l2;
        if (l == null) {
            return l1 != null ? l1 : l2;
        }
        ListNode head ;
        if (l1.val < l2.val){
            head = l1;
            l1 = l1.next;
        }
        else {
            head = l2;
            l2 = l2.next;
        }
        l = head;
        while (l1 != null || l2 != null) {
            if (l1 != null && l2 != null ){
                if (l1.val < l2.val) {

                    l.next = l1;
                    l = l.next;
                    l1 = l1.next;

                }else {
                    l.next = l2;
                    l = l.next;
                    l2 = l2.next;
                }
            }else {
                ListNode l0 = l1 != null? l1 : l2;
                l.next = l0;
                break;
            }
        }
        return head;
    }
}


//----------------------------------------
//记得判断链表是否有循环,可以用一快一慢两个指针,寻找中点也可以使用一快一慢两指针,降低了计算链表长度的时间

public class MergeSortList {

    public ListNode sortList(ListNode left){

        if (left == null || left.next == null) return left;

            ListNode pMid = left;//slow pointer  every 2 step
            ListNode pEnd = left;// fast pointer  every 1 step
            pEnd = pEnd.next;

            while (pEnd != null){
                pEnd = pEnd.next;

                if (pEnd != null){
                    pMid = pMid.next;
                    pEnd = pEnd.next;
                }
            }// breaks when pMid go to the middle

            pEnd = pMid.next;
            pMid.next = null;
            pMid = pEnd;

            ListNode p1 = sortList(pMid);
            ListNode p2 = sortList(left);
            return mergeTwoLists(p1, p2);//p1,p2不会是null
    }




    public ListNode mergeTwoLists(ListNode head1, ListNode head2) {//已经确定head1,head2都不会是null
        ListNode tail = new ListNode(0);
        ListNode h = tail;
        while (head1 != null && head2 != null){
            if (head1.val < head2.val){
                tail.next=head1;
                head1=head1.next;
            } else{
                tail.next=head2;
                head2=head2.next;
            }
            tail = tail.next;
        }

        tail.next=(head1 != null)?head1:head2;
        return h;

    }
}



快速排序:

最优复杂度为o(nlogn),此时 左右两子树比较平衡
最差复杂度为o(n2) ,此时只有一个子树,左子树或者右子树,例如1#2#3#4#5#6#….
—————————————-

如果按照数组的实现方式,那么可以用k&r的单方向一次遍历,但是要不停的交换结点,链表如果只交换结点的数值,可行,但是感觉意义不大,交换结点过于复杂,特殊情况较多。链表的特点在于可以快速增删,但不便于遍历。

实现思想如下:

把要排序的链表h分为两部分,h的头结点head作为比较结点
l1 链表所有结点值大于head.val

l2  链表所有结点值小于head.val
然后return l1 + head + l2

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

public class SortList {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;// throw new IllegalArgumentException("no list");
        ListNode pHead1 = new ListNode(0);
        ListNode pHead2 = new ListNode(0);

        ListNode p = head.next;
        ListNode tail1 = pHead1;
        ListNode tail2 = pHead2;

        while (p != null){
            if (p.val >= head.val){
                tail1.next = p;
                p = p.next;
                tail1 = tail1.next;
                tail1.next =null;
            }else {
                tail2.next = p;
                p = p.next;
                tail2 = tail2.next;
                tail2.next = null;
            }
        }


         ListNode l1 = sortList(pHead1.next);
         ListNode l2 = sortList(pHead2.next);

        tail1 = l1;
        while (tail1 != null) {
            if (tail1.next == null)
                break;
            tail1 = tail1.next;

        }
        if (l1 != null)
            tail1.next = head;
        else
            l1 = head;
         head.next = l2;

        return l1;

    }

}


 

Tagged on: , , ,

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>