[牛客top101]合并两个有序链表

---

---

1.题目描述

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。
数据范围： 10000≤n≤1000，−1000≤节点值≤1000
要求：空间复杂度 O(1)，时间复杂度 O(n)

2.题目分析

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

由于谁的值更小是不确定的,所以,为了避免头结点不确定的情况,我们这里定义一个节点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

3. 完整代码

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public 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;
    }
}

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