算法题--合并有序链表数组

合并排序链表（有序链表数组的合并）

### 题目：

给定一个链表数组，每个链表都已经按升序排列。请将所有链表合并到一个升序链表中，返回合并后的链表。

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

来源：[力扣（LeetCode）](https://leetcode-cn.com/problems/vvXgSW)

### 解法1：

自己写的，不知道用了什么思想。总的来说就是把链表数组横向看，横切面上n个元素比较，然后拿出最小值，拿到的那个位置后移。一直比较到n个位置都为null就算比完了。

```java
package com.example.demo.core.Leecode;

import java.util.PriorityQueue;

/**
 * @author: HanXu
 * on 2022/2/24
 * Class description: Head头结点也储存数据（LeeCode这道题的规则）
 */
public class LinkedDemo {

static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

public static void main(String[] args) {
        int[] arr1 = {1, 4, 5};
        int[] arr2 = {1, 3, 4};
        int[] arr3 = {2, 6,};
        ListNode head1 = buildLinked(arr1);
        ListNode head2 = buildLinked(arr2);
        ListNode head3 = buildLinked(arr3);
        printLinked(head1);
        printLinked(head2);
        printLinked(head3);

ListNode[] listNodes = new ListNode[3];
        listNodes[0] = head1;
        listNodes[1] = head2;
        listNodes[2] = head3;
        ListNode node = mergeKLists(listNodes);

printLinked(node);
        /*
        1 4 5
        1 3 4
        2 6
        1 1 2 3 4 4 5 6
         */
    }

/**
     * 合并排序链表：
     * 给定一个链表数组，每个链表都已经按升序排列。请将所有链表合并到一个升序链表中，返回合并后的链表。
     * 输入：lists = [[1,4,5],[1,3,4],[2,6]]
     * 输出：[1,1,2,3,4,4,5,6]
     * 解释：链表数组如下：
     * [
     *   1->4->5,
     *   1->3->4,
     *   2->6
     * ]
     * 将它们合并到一个有序链表中得到。
     * 1->1->2->3->4->4->5->6
     *
     * 来源：力扣（LeetCode）https://leetcode-cn.com/problems/vvXgSW
     * @param lists
     * @return
     */
    public static ListNode mergeKLists(ListNode[] lists) {
        ListNode head = new ListNode();
        ListNode pNode = head;
        int len = lists.length;

while (true) {
            int min = 0;
            int minIndex = 0;
            boolean flag = false;

//先找出每个列上不为空的一个node，假设该组中最小的是这个node
            for (int i = 0; i < len; i++) {
                if (lists[i] != null) {
                    min = lists[i].val;
                    minIndex = i;
                }
            }

//比较该组，更新最小node的值和索引
            for (int i = 0; i < len; i++) {
                if (lists[i] != null) {
                    flag = true;
                    if (lists[i].val < min) {
                        min = lists[i].val;
                        minIndex = i;
                    }
                }
            }
            //重点是横向切面比较，每次比较完lists[minIndex] = lists[minIndex].next;所以下次比较时，下一组还是lists[0]、lists[1]、lists[2]
            if (flag) {
                pNode.next = lists[minIndex];
                pNode = pNode.next;
                lists[minIndex] = lists[minIndex].next;
            } else {
                break;
            }
        }
        return head.next;
    }

/**
     * 打印链表
     * @param head
     */
    private static void printLinked(ListNode head) {
        ListNode pNode = head;
        while (pNode != null) {
            System.out.print(pNode.val + " ");
            pNode = pNode.next;
        }
        System.out.println();
    }

/**
     * 构建链表
     * @param arr
     * @return 返回的是第一个元素，而不是head
     */
    private static ListNode buildLinked(int[] arr) {
        ListNode head = new ListNode();
        ListNode pNode = head;
        for (int i = 0; i < arr.length; i++) {
            ListNode listNode = new ListNode(arr[i]);
            pNode.next = listNode;
            pNode = pNode.next;
        }
        return head.next;
    }
}
```

### 解法2：

使用优先队列，一种“偷懒”的方法，先把所有节点存进优先队列（村的过程会自动排序）。然后拿出来串成链表，返回。

```java
	//其他公共方法和上面一样，省略... 
	public static void main(String[] args) {
        int[] arr1 = {-2,-1,-1,-1};
        int[] arr2 = {};
        ListNode head1 = buildLinked(arr1);
        ListNode head2 = buildLinked(arr2);
        printLinked(head1);
        printLinked(head2);

ListNode[] listNodes = new ListNode[2];
        listNodes[0] = head1;
        listNodes[1] = head2;
        ListNode node = mergeKLists2(listNodes);

printLinked(node);
        /*
        -2 -1 -1 -1

-2 -1 -1 -1
         */
    }

/**
     * 使用优先队列
     * @param lists
     * @return
     */
    public static ListNode mergeKLists2(ListNode[] lists) {
        //从小到大
        PriorityQueue<ListNode> priorityQueue = new PriorityQueue<>(((o1, o2) -> (o1.val - o2.val)));
        //依次将每个节点放入优先队列，自动排序
        for (int i = 0; i < lists.length; i++) {
            ListNode listNode = lists[i];
            while (listNode != null) {
                priorityQueue.add(listNode);
                listNode = listNode.next;
            }
        }
        //拿出来串成链表
        ListNode head = new ListNode();
        ListNode pNode = head;
        while (!priorityQueue.isEmpty()) {
            ListNode listNode = priorityQueue.poll();
            //防止循环引用（node之前的next没有被破坏，链接新的next后有可能循环引用）
            listNode.next = null;
            pNode.next = listNode;
            pNode = pNode.next;
        }
        return head.next;
    }
```

算法题--合并有序链表数组

发表评论