【笔试真题】牛客真题：JZ25 合并两个排序的链表_jz25合并两个排序的链表 python

题目

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

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

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

分析

这道题,我们首先会想到的是,遍历两个链表的节点,谁的值小,就往后连.所以,这里有一个问题,要连在谁的后面呢?

由于谁的值更小是不确定的,所以,为了避免头结点不确定的情况,我们这里定义一个节点newHead1,谁的值小,就直接连在newHead后面.这样,返回头结点时,就返回newHead.next就行.

ListNode newHead = new ListNode(-1);
1

之后,就谁的值小,谁就往newHead后面连即可.

由于newHead不能改变,所以定义一个tmp去把值小的节点连到后面

ListNode tmp = newHead;
     while(head1 != null && head2 != null){
         if(head1.val <= head2.val){
             tmp.next = head1;
             head1 = head1.next;
         }else{
             tmp.next = head2;
             head2 = head2.next;
         }
         tmp = tmp.next;
     }
1
2
3
4
5
6
7
8
9
10
11

最后,看谁的节点还没走完,连到tmp后面即可

if(head1 != null){
    tmp.next = head1;
}
if(head2 != null){
    tmp.next = head2;
}
1
2
3
4
5
6

代码

代码：GitHub

/**
 * @author hanson
 * @date 2024/3/12 22:40
 */
public class JZ25 {
    /*
     * 输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。
     * 如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，所以对应的输出为{1,2,3,4,5,6}，转换过程如下图所示：
     * */
    // 定义链表节点类
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
            this.next = null;
        }
    }

    public static ListNode Merge(ListNode head1, ListNode head2) {
        //谁比较小,谁就是next
        //循环结束后,谁不为空,就接着往后面放
        ListNode newHead = new ListNode(-1);
        ListNode tmp = newHead;
        while (head1 != null && head2 != null) {
            if (head1.val <= head2.val) {
                tmp.next = head1;
                head1 = head1.next;
            } else {
                tmp.next = head2;
                head2 = head2.next;
            }
            tmp = tmp.next;
        }
        if (head1 != null) {
            tmp.next = head1;
        }

        if (head2 != null) {
            tmp.next = head2;
        }

        return newHead.next;
    }

    public static void main(String[] args) {
        // 创建第一个链表: 1 -> 3 -> 5 -> null
        ListNode head1 = new ListNode(1);
        head1.next = new ListNode(3);
        head1.next.next = new ListNode(5);

        System.out.println("head1:");
        printList(head1);

        // 创建第二个链表: 2 -> 4 -> 6 -> null
        ListNode head2 = new ListNode(2);
        head2.next = new ListNode(4);
        head2.next.next = new ListNode(6);

        System.out.println("head2:");
        printList(head2);

        ListNode merge = Merge(head1, head2);

        System.out.println("merge:");
        printList(merge);

    }

    // 打印链表的方法
    public static void printList(ListNode head) {
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
}
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

代码运行结果：

head1:
1 -> 3 -> 5 -> null
head2:
2 -> 4 -> 6 -> null
merge:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

Process finished with exit code 0
1
2
3
4
5
6
7
8