牛客网高频算法题系列-BM12-单链表的排序
题目形容
形容
原题目见：BM12 单链表的排序
解法一：数组排序
首先判断如果链表为空或者只有一个结点，则不须要排序，间接返回原链表。
否则，应用额定空间进行排序，处理过程如下：
- 首先遍历链表，将所有结点值暂存在一个List中；
- 而后，应用库函数将List排序（也能够应用各种排序算法进行排序）；
- 最初，将排序后的结点值结构成新的链表并返回。
解法二：归并排序
应用递归的形式，将原链表排序，递归处理过程如下：
- 首先也是要判断如果链表为空或者只有一个结点，则不须要解决，间接返回原链表；
- 而后，应用快慢指针寻找链表的中点地位；
- 而后，递归调用别离排序中点左右的两个链表；
- 而后，将左右链表合并；
- 最初，返回合并后的链表。
代码
import java.util.ArrayList;import java.util.Collections;import java.util.List;public class Bm012 { /** * 数组排序 * * @param head ListNode类 the head node * @return ListNode类 */ public static ListNode sortInList(ListNode head) { if (head == null || head.next == null) { return head; } List<Integer> nodes = new ArrayList<>(); while (head != null) { nodes.add(head.val); head = head.next; } // 应用库函数将数组排序 Collections.sort(nodes); ListNode newHead = new ListNode(-1); ListNode cur = newHead; for (Integer val : nodes) { cur.next = new ListNode(val); cur = cur.next; } return newHead.next; } /** * 归并排序 * * @param head ListNode类 the head node * @return ListNode类 */ public static ListNode sortInList2(ListNode head) { if (head == null || head.next == null) { return head; } // 应用快慢指针寻找链表的中点地位 ListNode fast = head.next, slow = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } ListNode tmp = slow.next; slow.next = null; // 递归左右两边进行排序 ListNode left = sortInList(head); ListNode right = sortInList(tmp); // 创立新的链表 ListNode newHead = new ListNode(-1); ListNode cur = newHead; // 合并left和right链表 while (left != null && right != null) { if (left.val < right.val) { cur.next = left; left = left.next; } else { cur.next = right; right = right.next; } cur = cur.next; } cur.next = left != null ? left : right; return newHead.next; } public static void main(String[] args) { ListNode head = ListNode.testCase5(); System.out.println("原链表"); ListNode.print(head); System.out.println("排序后的链表"); ListNode.print(sortInList(head)); ListNode.print(sortInList2(head)); }}$1.01^{365} ≈ 37.7834343329$
$0.99^{365} ≈ 0.02551796445$
置信保持的力量！