【算法面试必刷Java版四】合并两个排序的链表

盲目刷题，浪费大量时间，博主这里推荐一个面试必刷算法题库，刷完足够面试了。传送门：牛客网面试必刷TOP101

🏄🏻作者简介：CSDN博客专家，华为云云享专家，阿里云专家博主，疯狂coding的普通码农一枚

    

🚴🏻‍♂️个人主页：莫逸风

    

👨🏻‍💻专栏题目地址👉🏻牛客网面试必刷TOP101👈🏻

    

🇨🇳喜欢文章欢迎大家👍🏻点赞🙏🏻关注⭐️收藏📄评论↗️转发

题目：合并两个排序的链表

描述：

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

数据范围： 0≤n≤1000，−1000≤节点值≤1000
要求：空间复杂度 O(1)，时间复杂度 O(n)

如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，所以对应的输出为{1,2,3,4,5,6}，转换过程如下图所示：

或输入{-1,2,4},{1,3,4}时，合并后的链表为{-1,1,2,3,4,4}，所以对应的输出为{-1,1,2,3,4,4}，转换过程如下图所示：

思路：

顺序迭代两个链表，将比较后较小的值的节点放到结果链表中，直到有一个链表迭代完全，结果链表的next则是另一个链表。

1. 创建一个节点-1作为结果链表。
2. 创建两个节点cur1,cur2分别标识两个链表遍历到的节点

代码：

public class BM04 {
    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(3);
        ListNode listNode3 = new ListNode(5);
        ListNode listNode4 = new ListNode(2);
        ListNode listNode5 = new ListNode(4);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = null;
        listNode4.next = listNode5;
        listNode5.next = null;
        ListNode result = Merge(listNode1,listNode4);
        while (result!=null){
            System.out.println(result.val);
            result = result.next;
        }
    }

    public static ListNode Merge(ListNode list1, ListNode list2) {
        ListNode pre = new ListNode(-1);
        ListNode cur = pre;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                cur.next = list1;
                list1 = list1.next;
            }else {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        if (list1!=null){
            cur.next = list1;
        }else {
            cur.next = list2;
        }
        return pre.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

推荐牛客网面试必刷算法题库，刷完足够面试了。传送门：牛客网面试必刷TOP101