这两天在网上刷算法题，做着做着发现关于链表的题目简直不要太多，

先上一题原题，难度：困难

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:[
  1->4->5,
  1->3->4,
  2->6
]输出: 1->1->2->3->4->4->5->6

首先我所做的的链表是一种根据元素节点逻辑关系排列起来的一种数据结构。利用链表可以保存多个数据，链表和数组的区别在于，数组的长度是固定的，而实际应用中会经常遇到的长度都是不确定的

是不是看起来有点眼熟，然后我翻开了880，没错，这不是和集合一样吗，然后翻书，查资料

链表是一种数据结构

LinkedList就是以链表为数据结构的一种集合

而ArrayList则是以数组为数据结构的集合

懂了！

之后就好做了

关于这道题，其实有好几种解法

第一种：暴力

遍历所有链表，将所有节点的值放到一个数组中。
将这个数组排序，然后遍历所有元素得到正确顺序的值。
用遍历得到的值，创建一个新的有序链表。

第二种：逐一比较

比较K个节点，然后找到最小的那个数的节点
将选中的节点接在最终节点最后
循环上面的步骤

第三种：两两合并

将两个链表合并成一个链表

class Solution {
    public ListNode mergeTwoLists(ListNode L1, ListNode L2) {
        if (L2 == null) {
            return L1;
        }
        else if (L1 == null) {
            return L2;
        }
        else if (L1.val < L2.val) {
            L1.next = mergeTwoLists(L1.next, L2);
            return L1;
        }
        else {
            L2.next = mergeTwoLists(L1, L2.next);
            return l2;
        }
    }
}

(递归牛批！)

其实想通了以后就蛮简单的，说是困难的难度，其实主要就是考察链表的理解和应用

链表的应用在日常生活中没有比数组低

ITPub博客

算法题中的链表

最新文章