【牛客-剑指offer-数据结构篇】JZ25 合并两个排序的链表三种思路 Java实现

1 网站链接

https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337

2 题目

在这里插入图片描述

import java.util.*;
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

3 注意点

两个链表的长度可能是不一样的，题目中只说了单个链表的长度为n
- 我一开始看成两个链表长度为n，就以为两个链表长度一样了
n的取值范围是0到1000，0和1000是可以取到的，所以链表的长度可能为0，即形参部分list1和list2可能为null

4 解题思路

由于两个链表的长度都可能为零，也就是传入的形参可能为null，所以将题目分为以下四种情况

list1 = null，list2 != null（特殊情况）
list1 != null，list2 = null（特殊情况）
list1 = null，list2 = null（特殊情况）
list1 != null，list2 != null（正常情况）

4.1 三种特殊情况

我们在一开始就进行判断，哪一个形参是null

list1 = null && list2 != null ，则返回list2 ------（1）
list1 != null && list2 = null ，则返回list1 ------（2）
list1 = null && list2 = null ，则返回null -------（3）

（1）和（3）可以合并，只要list1=null，就返回list2

4.2 普通情况

4.2.1 方案一

按顺序遍历两个链表，依次比较两个链表中数值的大小，创建一个新链表

4.2.2 方案二

按顺序遍历两个链表，依次比较两个链表中数值的大小，在原有两个链表的基础上，修改next属性的值，将两个链表串联在一起

4.2.3 方案三

遍历两个链表，将链表中的值全部取出，放在ArrayList中，排序，再创建新的链表

5 答案

5.1 方案一代码（创建一个新链表）

import java.util.*;
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1, ListNode list2) {

        //情况一：list1为空，list2不为空，返回list2
        //情况二：list1为空，list2为空，返回null
        //情况三：list1不为空，list2为空，返回list1
        
        if (list1 == null){
            return list2;
        }

        if (list2 == null){
            return list1;
        }

        //情况四：list1不为空，list2不为空，顺序遍历，比较生成新链表
        ListNode pre = null;
        ListNode node = null;
        ListNode head = null;
        while (list1 != null && list2 != null) {
            //判断当前两个链表中的特定节点，哪个值更小，把更小的取出
            if (list1.val <= list2.val) {
                node = new ListNode(list1.val);
                list1 = list1.next;
            } else {
                node = new ListNode(list2.val);
                list2 = list2.next;
            }
            //判断是否已经创建新链表
            if (head == null) {
                pre = node;
                head = node;
            } else {
                pre.next = node;
                pre = node;
            }
        }

        //list2提前遍历完
        if (list1 != null) {
            pre.next = list1;
        }

        //list1提前遍历完
        if (list2 != null) {
            pre.next = list2;
        }
        return head;

    }
}
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

5.2 方案二代码（改变两个链表的指针，将两个链表和成一个链表）

import java.util.*;
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1, ListNode list2) {

        //情况一：list1为空，list2不为空，返回list2
        //情况二：list1为空，list2为空，返回null
        //情况三：list1不为空，list2为空，返回list1

        if (list1 == null){
            return list2;
        }

        if (list2 == null){
            return list1;
        }

        //情况四：list1不为空，list2不为空，顺序遍历，比较生成新链表
        ListNode head = new ListNode(-1);
        ListNode node = head;
        while (list1 != null && list2 != null) {
            //判断当前两个链表中的特定节点，哪个值更小，把更小的取出
            if (list1.val <= list2.val) {
                node.next = list1;
                list1 = list1.next;
                node = node.next;
            } else {
                node.next = list2;
                list2 = list2.next;
                node = node.next;
            }
        }

        //list2提前遍历完
        if (list1 != null) {
            node.next = list1;
        }

        //list1提前遍历完
        if (list2 != null) {
            node.next = list2;
        }
        return head.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

图解