提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  .Net

当前栏目

合并k个已排序的链表

2023-02-18 16:36:15 时间

题目：

思路：

解法用了三种：
    1，采用搭建小顶堆的方式通过把节点塞入堆内自动排序，然后取出最小值，直至堆内为空，元素加入堆中的时间复杂度为O（longk），总共有kn个元素加入堆中，因此，时间复杂度是O（nklogk），空间复杂度的话是O（K），因为堆内存放数据量是根据有多少个链表来的
    2，链表1、2合并，然后其结果12和3合并，以此类推，最后是123--k-1和k合并。假设每个链表的平均长度是n，则1、2合并，遍历2n个节点；12结果和3合并，遍历3n个节点；....123...k-1的结果和k合并，遍历kn个节点，总共遍历n(2+3+4+....k)=n*(k^2+k-2)/2。
这种方法的时间复杂度是O(n*(k^2+k-2)/2)=O(nk^2)。
    3，是使用归并思路，先两两将小的链表合并成更大一点的链表，然后将更大的链表再合并。
下面是提交的结果，第一次是小顶堆的方案，第二次是暴力拼接的方案，第三次是归并思路的方案

代码示例：

import java.util.ArrayList;
import java.util.PriorityQueue;
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}
public class Solution {
    public static void main(String[] args) {
        ListNode arr1 = new ListNode(1);
        ListNode end1 = arr1;
        ListNode temp1 = arr1;
        ListNode arr2 = new ListNode(4);
        ListNode end2 = arr2;
        ListNode temp2 = arr2;
        ListNode arr3 = new ListNode(9);
        ListNode end3 = arr3;
        ListNode temp3 = arr3;
        ListNode arr4 = new ListNode(17);
        ListNode end4 = arr4;
        ListNode temp4 = arr4;
        ArrayList<ListNode> lists = new ArrayList<ListNode>();
        for (int i = 2; i < 4; i++) {
            ListNode temp = new ListNode(i);
            temp1.next = temp;
            temp1 = temp;
        }
        OutPutLinkedList(end1);
        for (int i = 5; i < 8; i++) {
            ListNode temp = new ListNode(i);
            temp2.next = temp;
            temp2 = temp;
        }
        OutPutLinkedList(end2);
        for (int i = 10; i < 16; i++) {
            ListNode temp = new ListNode(i);
            temp3.next = temp;
            temp3 = temp;
        }
        OutPutLinkedList(end3);
        for (int i = 18; i < 25; i++) {
            ListNode temp = new ListNode(i);
            temp4.next = temp;
            temp4 = temp;
        }
        OutPutLinkedList(end4);
        lists.add(null);
        lists.add(null);
//        lists.add(arr1);
//        lists.add(arr2);
//        lists.add(arr3);
//        lists.add(arr4);
        ListNode result = mergeKLists(lists);
        OutPutLinkedList(result);
    }
    /**
     * 利用归并的思想将两个小的先行组合成一个大的，如【0,1,2,3,4,5】六条，0与3先排序，1与4,2与5,
     * 然后形成新的【0,1,2】，再0与2排序，最后把1也合并了。
     *
     * @param lists
     * @return
     */
    public static ListNode mergeKLists(ArrayList<ListNode> lists) {
        int len = lists.size();
        if (lists.size() == 0)
            return null;
        while (len > 1) {
            int k = (len + 1) >> 1;
            for (int i = 0; i < len / 2; i++) {
                lists.set(i, mergeTwo(lists.get(i), lists.get(i + k)));
            }
            len = k;
        }
        return lists.get(0);
    }
    /**
     * 使用暴力的方法把每一条都加进去合并成为一条
     *
     * @param lists
     * @return
     */
    public static ListNode mergeKLists2(ArrayList<ListNode> lists) {
        if (lists.size() == 0)
            return null;
        if (lists.size() == 1)
            return lists.get(0);
        ListNode result = lists.get(0);
        for (int i = 1; i < lists.size(); i++) {
            result = mergeTwo(result, lists.get(i));
        }
        return result;
    }
    /**
     * 将两个有序链表进行合并
     *
     * @param head1
     * @param head2
     * @return
     */
    public static ListNode mergeTwo(ListNode head1, ListNode head2) {
        if (head1 == null)
            return head2;
        if (head2 == null)
            return head1;
        ListNode new_list = new ListNode(0);
        ListNode temp = new_list;
        while (head1 != null || head2 != null) {
            if (head1 != null && head2 != null) {
                if (head1.val < head2.val) {
                    temp.next = head1;
                    head1 = head1.next;
                } else {
                    temp.next = head2;
                    head2 = head2.next;
                }
            } else if (head1 != null) {
                temp.next = head1;
                head1 = head1.next;
            } else if (head2 != null) {
                temp.next = head2;
                head2 = head2.next;
            }
            temp = temp.next;
        }
        //为什么返回的是下一个节点？原因在于，在上面创建了一个新的节点，而新的节点后面的才是将两个链表合并排序的东西
        //所以你要把自己创建的那个节点给清除掉
        return new_list.next;
    }
    /**
     * 利用小顶堆思想的合并多个已排序链表
     *
     * @param lists
     * @return
     */
    public static ListNode mergeKLists1(ArrayList<ListNode> lists) {
        ListNode result = new ListNode(0);
        ListNode temp = result;
        //优先队列，即堆，使用小顶堆
        PriorityQueue<ListNode> nodeHeap = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val;
            }
        });
        //将链表的投节点添加到小顶堆中
        for (ListNode h : lists) {
            if (null != h) {
                nodeHeap.add(h);
            }
        }
        //从堆中拿出元素链表接到结果链表中，并查看该链表是否有下一节点，有的话将下一节点加入堆中，重复操作直至所有堆清空
        while (!nodeHeap.isEmpty()) {
            ListNode node = nodeHeap.poll();
            temp.next = node;
            temp = node;
            if (null != node.next) {
                nodeHeap.add(node.next);
            }
        }
        return result.next;
    }
    /**
     * 打印链表，用于输出查看
     *
     * @param head
     */
    public static void OutPutLinkedList(ListNode head) {
        ListNode temp = head;
        while (null != temp) {
            System.out.print(temp.val);
            if (null != temp.next) {
                System.out.print(" -> ");
            }
            temp = temp.next;
        }
        System.out.println();
    }
}

相关文章