我是靠谱客的博主 顺利灯泡,这篇文章主要介绍【DS】链表面试热题之合并链表及其变体,现在分享给大家,希望可以做个参考。

文章目录

    • 一、合并两个有序链表
      • 题目描述
      • 思路分析:
      • 图示分析:
      • AC代码
    • 二、合并k个有序链表
      • 题目描述
      • 思路分析:
      • 几点注意:
      • 图示分析:
      • AC代码


合并有序链表核心思路:

双指针:分别遍历两个链表,然后链到总的链表上。


模板:

ListNode head = new ListNode(-1);
ListNode prev = head;
while (list1 != null && list2 != null) {
    if (list1.val <= list2.val) {
        prev.next = list1;
        list1 = list1.next;
    } else {
        prev.next = list2;
        list2 = list2.next;
    }
    prev=prev.next;
}
prev.next=(list1==null)?list2:list1;
return head.next;

一、合并两个有序链表

题目描述

1.输入两个递增的链表,单个链表的长度为n,合并这两个链表并使新链表中的节点仍然是递增排序的。OJ链接

思路分析:

  1. 比较两个链表当前引用的val值小的加入总的链,循环比较操作,循环条件是两个引用都不是空的,否则容易空指针异常。
  2. 循环终止的时候,肯定有一个结点不是空的这个时候我们需要单独操作,,然后让总的遍历的pre链上它
  3. 为了方便操作这里引用了一个虚拟头结点,返回的时候只要返回它的next值即可

图示分析:

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PXbrAMvb-1665134357599)(F:typora插图image-20221007161646165.png)]

AC代码

public ListNode Merge(ListNode list1, ListNode list2) {
    ListNode head = new ListNode(-1);
    ListNode prev = head;
    while (list1 != null && list2 != null) {
        if (list1.val <= list2.val) {
            prev.next = list1;
            list1 = list1.next;
        } else {
            prev.next = list2;
            list2 = list2.next;
        }
        prev=prev.next;
    }
    prev.next=(list1==null)?list2:list1;
    return head.next;
}

二、合并k个有序链表

题目描述

2.合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。OJ链接

思路分析:

  1. 给的顺序表,顺序表中的每个值是链表的每个头结点,所以循环条件是顺序表不为空
  2. 一个一个从表中拿出来,在调用我们之前定义的合并两个有序链表肯定行不通,这样不满足时间复杂度为O(nlogn),行不通。

几点注意:

  1. 注意导包
  2. int mid = left + (right - left) /2;可以通过,但是int mid = left + (right - left)>>1;没办法通过,原因未知,以后再说。

图示分析:

在这里插入图片描述

AC代码

public ListNode mergeKLists(ArrayList<ListNode> lists) {
    return divideMergeLists(lists,0,lists.size()-1);
}
private ListNode divideMergeLists(ArrayList<ListNode> lists, int left,int right) {
    if (left > right) {
        return null;
    } else if (left == right) {
        return lists.get(left);
    }
    int mid = left + (right - left) /2;
    return Merge(divideMergeLists(lists, left, mid), divideMergeLists(lists, mid+1, right));
}
private ListNode Merge(ListNode list1, ListNode list2) {
    ListNode head = new ListNode(-1);
    ListNode prev = head;
    while (list1 != null && list2 != null) {
        if (list1.val <= list2.val) {
            prev.next = list1;
            list1 = list1.next;
        } else {
            prev.next = list2;
            list2 = list2.next;
        }
        prev = prev.next;
    }
    prev.next = (list1 == null) ? list2 : list1;
    return head.next;
}

最后

以上就是顺利灯泡最近收集整理的关于【DS】链表面试热题之合并链表及其变体的全部内容,更多相关【DS】链表面试热题之合并链表及其变体内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(58)

评论列表共有 0 条评论

立即
投稿
返回
顶部