欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

单链表的归并排序和插入排序

程序员文章站 2024-03-17 23:50:28
...

由于最近在学习数据结构和算法,在牛客网 的在线编程题上遇到了对链表的相关排序操作,发现自己对链表这块还是理解不够深入,以前做过对数组进行排序,但链表的操作要比数组复杂一些,毕竟不能进行随机访问了,单链表得从头开始找。
下面是我通过在线编程(OJ)代码并附有注释。


1.单链表的归并排序

1.题目

Sort a linked list in O(n log n) time using constant space complexity.
对一个链表进行排序,要求时间复杂度为O(n log n)

2.解题思路

题目要求时间复杂度为nlog(n),所以选择了归并排序。归并排序最坏时间复杂度、平均时间复杂度、最快时间复杂度都为nlog(n)。它是一种稳定的排序算法。
链接:思路来源
来源:牛客网
单链表的归并排序和插入排序

2.1 拆分链表,找到中间节点

快慢指针的方式,快指针移动两位,慢指针移动一位。

    /** 查找中间结点 */
public ListNode findMidNode(ListNode head){
    ListNode p= head;
    ListNode q=head.next;
    while (q != null && q.next != null) {
        p = p.next;
        q = q.next.next;
    }
    return p;
}

2.2分治,分别处理每个链表

    ListNode midNode =findMidNode(head);
    ListNode record = midNode.next;
    midNode.next = null; //断开两个链表的连接
    ListNode left = MySort(head, midNode);
    ListNode right = MySort(record, end);

2.3合并

/** 合并左右链表 */
private ListNode merge(ListNode left, ListNode right) {
    if(left==null)return right;
    if(right==null)return left;
    ListNode newhead = null;
    newhead=new ListNode(0);
    ListNode temp = newhead;
    while (left != null && right != null) {
        if (left.val > right.val) {
            temp.next= right; 
            right= right.next;
        } else {
            temp.next= left;
            left = left.next;
        }   
        temp=temp.next;
    }
    temp.next=(left==null)?right:left;
    return newhead.next;
}

3. 完整代码

/**
 * Definition for singly-linked list. 
 * class ListNode {
 *  int val; ListNode next;
 * ListNode(int x) {
 *  val = x; next = null;
 *   }
 *} //排序算法选择归并排序
 */
public class Solution {
    private ListNode indexNode =new ListNode(Integer.MAX_VALUE); 
    public ListNode sortList(ListNode head) {
        if (head == null) {
            return head;
        }
        return MySort(head, null);
    }

    private ListNode MySort(ListNode head, ListNode end) {
        if(head==end){
            return head;
        }
        ListNode midNode =findMidNode(head);
        ListNode record = midNode.next;
        midNode.next = null;
        ListNode left = MySort(head, midNode);
        ListNode right = MySort(record, end);
        return merge(left, right);
    }
     /** 查找中间结点 */
    public ListNode findMidNode(ListNode head){
        ListNode p= head;
        ListNode q=head.next;
        while (q != null && q.next != null) {
            p = p.next;
            q = q.next.next;
        }
        return p;
    }
    /** 合并左右链表 */
    private ListNode merge(ListNode left, ListNode right) {
        if(left==null)return right;
        if(right==null)return left;
        ListNode newhead = null;
        newhead=new ListNode(0);
        ListNode temp = newhead;
        while (left != null && right != null) {
            if (left.val > right.val) {
                temp.next= right; 
                right= right.next;
            } else {
                temp.next= left;
                left = left.next;
            }   
            temp=temp.next;
        }
        temp.next=(left==null)?right:left;
        return newhead.next;
    }

    public static void main(String[] args) {
        ListNode list = new ListNode(4);
        ListNode head = list;
        head.next = new ListNode(2);
        head.next.next = new ListNode(1);
        head.next.next.next = new ListNode(3);
        Solution solution = new Solution();
        ListNode result = solution.sortList(head);
        while (result != null) {
            System.out.print(result.val + "\t");
            result = result.next;
        }
    }

    public void display(ListNode result) {
        while (result != null) {
            System.out.print(result.val + "\t");
            result = result.next;
        }
        System.out.println();
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

2.单链表的直接插入排序

1.题目

Sort a linked list using insertion sort.

2.注意事项

每次的插入操作时,需要保留下一结点。
然后用伪首结点该结点值为最小值,将他们串联起来。

完整代码

public class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) // 链表为空或者仅一个结点
            return head;
        ListNode saveNode = new ListNode(Integer.MIN_VALUE);
        // ListNode current =head;
        ListNode previous = saveNode;
        while (head != null) {
            ListNode next = head.next;
            previous = saveNode; // 每次都从新链表的头结点进行遍历
            while (previous.next != null && previous.next.val < head.val) {
                previous = previous.next;
            }

            if (previous == saveNode) { // 链表为空时
                head.next = previous.next;
                previous.next=head;
            } else if(previous.next==null){  //尾部结点时
                head.next = previous.next;
                previous.next=head;
            }
            else {  //中间插入
                ListNode nextnext=previous.next;
                head.next=nextnext;
                previous.next=head;
            }
            head = next;
        }
        return saveNode.next;
    }

    public void display(ListNode node) {
        while (node != null) {
            System.out.print(node.val + "\t");
            node = node.next;
        }
    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }

}