关于java:牛客网高频算法题系列BM12单链表的排序

牛客网高频算法题系列 -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$
置信保持的力量！