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

男娘i 2022-06-13 04:21 200阅读 0赞

由于最近在学习数据结构和算法，在牛客网 的在线编程题上遇到了对链表的相关排序操作,发现自己对链表这块还是理解不够深入，以前做过对数组进行排序，但链表的操作要比数组复杂一些，毕竟不能进行随机访问了，单链表得从头开始找。  
下面是我通过在线编程（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)。它是一种稳定的排序算法。  
链接：[思路来源][Link 1]  
来源：牛客网  
![这里写图片描述][SouthEast]

#### 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;
        }
    
    }

[Link 1]: https://www.nowcoder.com/questionTerminal/d75c232a0405427098a8d1627930bea6
[SouthEast]: /images/20220613/93bf5cf4b1d2429b8dc974e8485eb8f7.png