牛客网高频算法题系列-BM12-单链表的排序

题目描述

描述

原题目见：BM12 单链表的排序

解法一：数组排序

首先判断如果链表为空或者只有一个结点，则不需要排序，直接返回原链表。

否则，使用额外空间进行排序，处理过程如下：

  • 首先遍历链表，将所有结点值暂存在一个List中；
  • 然后，使用库函数将List排序（也可以使用各种排序算法进行排序）；
  • 最后，将排序后的结点值构造成新的链表并返回。

解法二：归并排序

使用递归的方式，将原链表排序，递归处理过程如下：

  • 首先也是要判断如果链表为空或者只有一个结点，则不需要处理，直接返回原链表；
  • 然后，使用快慢指针寻找链表的中点位置；
  • 然后，递归调用分别排序中点左右的两个链表；
  • 然后，将左右链表合并；
  • 最后，返回合并后的链表。

代码

  1. import java.util.ArrayList;
  2. import java.util.Collections;
  3. import java.util.List;
  5. public class Bm012 {
  6.     /**
  7.      * 数组排序
  8.      *
  9.      * @param head ListNode类 the head node
  10.      * @return ListNode类
  11.      */
  12.     public static ListNode sortInList(ListNode head) {
  13.         if (head == null || head.next == null) {
  14.             return head;
  15.         }
  16.         List<Integer> nodes = new ArrayList<>();
  17.         while (head != null) {
  18.             nodes.add(head.val);
  19.             head = head.next;
  20.         }
  21.         // 使用库函数将数组排序
  22.         Collections.sort(nodes);
  23.         ListNode newHead = new ListNode(-1);
  24.         ListNode cur = newHead;
  25.         for (Integer val : nodes) {
  26.             cur.next = new ListNode(val);
  27.             cur = cur.next;
  28.         }
  29.         return newHead.next;
  30.     }
  32.     /**
  33.      * 归并排序
  34.      *
  35.      * @param head ListNode类 the head node
  36.      * @return ListNode类
  37.      */
  38.     public static ListNode sortInList2(ListNode head) {
  39.         if (head == null || head.next == null) {
  40.             return head;
  41.         }
  42.         // 使用快慢指针寻找链表的中点位置
  43.         ListNode fast = head.next, slow = head;
  44.         while (fast != null && fast.next != null) {
  45.             slow = slow.next;
  46.             fast = fast.next.next;
  47.         }
  48.         ListNode tmp = slow.next;
  49.         slow.next = null;
  50.         // 递归左右两边进行排序
  51.         ListNode left = sortInList(head);
  52.         ListNode right = sortInList(tmp);
  53.         // 创建新的链表
  54.         ListNode newHead = new ListNode(-1);
  55.         ListNode cur = newHead;
  56.         // 合并left和right链表
  57.         while (left != null && right != null) {
  58.             if (left.val < right.val) {
  59.                 cur.next = left;
  60.                 left = left.next;
  61.             } else {
  62.                 cur.next = right;
  63.                 right = right.next;
  64.             }
  65.             cur = cur.next;
  66.         }
  67.         cur.next = left != null ? left : right;
  69.         return newHead.next;
  70.     }
  72.     public static void main(String[] args) {
  73.         ListNode head = ListNode.testCase5();
  74.         System.out.println("原链表");
  75.         ListNode.print(head);
  77.         System.out.println("排序后的链表");
  78.         ListNode.print(sortInList(head));
  79.         ListNode.print(sortInList2(head));
  80.     }
  81. }

牛客网高频算法题系列-BM12-单链表的排序 - 图1
牛客网高频算法题系列-BM12-单链表的排序 - 图2
相信坚持的力量！