Java教程

算法 - 归并排序

本文主要是介绍算法 - 归并排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

算法 - 归并排序

递归法

  1. 使用快慢指针,找到中间节点,当只有一个节点的时候,递归失效。
  2. 递归左部节点的头节点和右部节点的头节点。
  3. 新建前驱节点,并创建指向前驱节点的头指针,对比左右两侧节点大小,然后插入到前驱节点。

参考代码

class Solution {
    public ListNode sortList(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 = sortList(head);//操作两个返回的头节点,d
        ListNode right = sortList(tmp);
        ListNode h = new ListNode(0);
        ListNode res = h;
        while (left != null && right != null) {
            if (left.val < right.val) {
                h.next = left;
                left = left.next;
            } else {
                h.next = right;
                right = right.next;
            }
            h = h.next;
        }
        h.next = left != null ? left : right;
        return res.next;//返回虚拟头节点的下一个
    }
}
这篇关于算法 - 归并排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!