【经典面试题-LeetCode21：合并两个有序链表（附Java代码）】_leetcode 合并两个有序链表 java

一、题目描述

1.题目内容

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
原题链接：https://leetcode.cn/problems/merge-two-sorted-lists/

2.样例

需要注意，虽然样例中输入的两个列表是整数数组的形式，但其实官网的评测机内部将其分别先构建成以1为头节点的单链表（样例1为例），而传入mergeTwoLists方法的实参也正为每个链表的头节点。

二、解决方案

这道题在数据结构链表内容中属于是比较经典的，解这道题涉及到的知识点主要是以下两点：

• 不带头节点的单链表的创建，此时头节点就是链表的第一个节点；
• 单链表的插入节点操作（尾插法或头插法）；

1.算法流程

1）分析

对于两个不带头节点的有序单链表，通过依次比较各节点的数据大小，拼接合并得到新的有序单链表。
以样例1为例，分析其合并过程：

2）算法流程

大致流程就是从两个链表的头结点开始，依次比较对应节点数据的大小，根据比较结果拼接合并结果，具体地：

• 因为头结点不能动，所以设置两个辅助节点tempNode1、tempNode2分别指向输入链表的头结点list1和list2，即令tempNode1=list1，tempNode2=list2，用于遍历链表；
• 创建合并结果链表res的头结点，用于后续节点的插入；
• 创建辅助节点tempNode，令tempNode=resNode，用于通过尾插法实现带头结点的单链表；
• 通过tempNode1、tempNode2从头遍历对应链表，此时：
  （1）若tempNode1.val<tempNode2.val，则将tempNode1所指向的节点通过tempNode插入结果链表，并将tempNode1向右移动一个位置，即tempNode.next=tempNode1、tempNode1=tempNode1.next；
  （2）反之，若tempNode1.val>=tempNode2.val，则将tempNode2所指向的节点通过tempNode插入结果链表，并将tempNode2向右移动一个位置，即tempNode.next=tempNode2、tempNode2=tempNode2.next；
  （3）然后移动链表res的辅助节点，令tempNode=tempNode.next；
  （4）循环（1-3）步，直到某个链表到达链尾停止循环比较，即tempNode1=null或tempNode2=null；
• 当某个链表到达链尾，跳出循环，但可能此时另一链表还有剩余节点，所以我们需要判断具体是哪个链表到达了链尾，然后将另一个链表的剩余节点直接插入到结果链表res中。比如， list1到达链尾，直接将list2的剩余节点插入到res中；
• 最后直接返回头结点resNode的next域所指向的节点，即含有数据域的第一个节点；

2.Java代码

在实现时，需要在进入mergeTwoLists方法一开始就考虑以下三种特殊情况：

• list1=null且list2=null，即l1=[]，l2=[]，此时 直接返回null；
• list1=null，list2!=null，即l1=[]，l2=[x,x,x,x…]，此时 直接返回list2；
• list1!=null，list2=null，即l1=[x,x,x,x…]，l2=[]，此时 直接返回list1；

此外，因为采用的是不带头节点的单链表，所以在传入实参时直接传入对应链表的第一个节点即可。

1）核心代码

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1==null && list2==null){  // l1=l2=[]
            return null;
        }

        if(list1 == null){ // l1=[],l2=[x,x,x,x,x...]
            return list2;
        }

        if(list2 == null){ // l1=[x,x,x,x,x...],l2=[]
            return list1;
        }
		
		// 链表头结点不能动，否则后续节点无法查找，所以需要设置各自对应的辅助节点
        ListNode tempNode1=list1;  // 令辅助节点为链表l1的头结点
        ListNode tempNode2=list2; // 令辅助节点为链表l2的头结点
        ListNode resNode=new ListNode(-1);  //创建合并结果链表的头结点
        ListNode tempNode=resNode;  // 令辅助节点为合并链表的头结点
		
		// 循环比较节点大小，并插入结果链表res中
        while (tempNode1!=null&&tempNode2!=null){
            if(tempNode1.val<tempNode2.val){
                tempNode.next=tempNode1;
                tempNode1=tempNode1.next;
            }else {
                tempNode.next=tempNode2;
                tempNode2=tempNode2.next;
            }
            tempNode=tempNode.next;
        }

        if(tempNode1==null){  // list1到达链尾，直接将list2的剩余节点插入到res中
            tempNode.next=tempNode2;
        }
        if(tempNode2==null){ // list2到达链尾，直接将list1的剩余节点插入到res中
            tempNode.next=tempNode1;
        }
        return resNode.next;  // 返回头结点resNode的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

2）完整测试代码

package com.north.leetcode;
/**
 * LeetCode21：合并两个有序链表
 */

import java.util.List;

public class mergeLinkList {
    public static void main(String[] args) {
        LinkedList list1=new LinkedList();
        ListNode node3=new ListNode(4);
        ListNode node2=new ListNode(2);
        ListNode node1=new ListNode(1);
        list1.insertByTail(node1);
        list1.insertByTail(node2);
        list1.insertByTail(node3);
        list1.printList();
        System.out.println("--------------------------------");
//        list1.printByCustom(node2);

        LinkedList list2=new LinkedList();
        ListNode node23=new ListNode(4);
        ListNode node22=new ListNode(3);
        ListNode node21=new ListNode(1);
        list2.insertByHead(node23);
        list2.insertByHead(node22);
        list2.insertByHead(node21);
        list2.printList();
        System.out.println("--------------------------------");
        new LinkedList().mergeTwoLists(node1,node21).printByCustom();
    }
}


class LinkedList{
    ListNode head;
    public LinkedList(){

    }
    // 尾插法
    public void insertByTail(ListNode node){
        if (head==null){
            head=node;
        }else {
            ListNode tempNode = head;
            while (tempNode.next != null) {
                tempNode = tempNode.next;
            }
            tempNode.next = node;
        }
    }

    // 头插法
    public void insertByHead(ListNode node){
        if (head != null) {
            node.next = head;
        }
        head=node;
    }
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1==null && list2==null){  // l1=l2=[]
            return null;
        }

        if(list1 == null){ // l1=[],l2=[x,x,x,x,x...]
            return list2;
        }

        if(list2 == null){ // l1=[x,x,x,x,x...],l2=[]
            return list1;
        }

        // 链表头结点不能动，否则后续节点无法查找，所以需要设置各自对应的辅助节点
        ListNode tempNode1=list1;  // 令辅助节点为链表l1的头结点
        ListNode tempNode2=list2; // 令辅助节点为链表l2的头结点
        ListNode resNode=new ListNode(-1);  //创建合并结果链表的头结点
        ListNode tempNode=resNode;  // 令辅助节点为合并链表的头结点

        // 循环比较节点大小，并插入结果链表res中
        while (tempNode1!=null&&tempNode2!=null){
            if(tempNode1.val<tempNode2.val){
                tempNode.next=tempNode1;
                tempNode1=tempNode1.next;
            }else {
                tempNode.next=tempNode2;
                tempNode2=tempNode2.next;
            }
            tempNode=tempNode.next;
        }

        if(tempNode1==null){  // list1到达链尾，直接将list2的剩余节点插入到res中
            tempNode.next=tempNode2;
        }
        if(tempNode2==null){ // list2到达链尾，直接将list1的剩余节点插入到res中
            tempNode.next=tempNode1;
        }
        return resNode.next;  // 返回头结点resNode的next域所指向的节点
    }

    // 遍历整个链表
    public void printList(){
        ListNode tempNode=head;
        while (tempNode!=null){
            System.out.println(tempNode);
            tempNode=tempNode.next;
        }
    }

    // 从指定的节点开始遍历
//    public void printByCustom(ListNode node){
//        ListNode tempNode=node;
//        while (tempNode!=null){
//            System.out.println(tempNode);
//            tempNode=tempNode.next;
//        }
//    }

}
// 定义链表节点
class ListNode{
    int val;
    ListNode next;

    public ListNode() {
    }

    public ListNode(int val) {
        this.val = val;
    }

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

    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val +
                '}';
    }

     //从指定的节点开始遍历
      public void printByCustom(){
         ListNode tempNode=this;
         while (tempNode!=null){
            System.out.println(tempNode);
             tempNode=tempNode.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
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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151