面试题17-合并两个排序的链表

Posted on Edited on In

题目

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

解题

合并过程（《剑指offer》）

非递归

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
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        // 注意这里不能传入null，也不能=null
        ListNode cur = new ListNode(0);
        // dummy head
        ListNode dummy = cur;
        if (list1 == null){
            return list2;
        }
        if (list2 == null){
            return list1;
        }
        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 if (list2 != null){
            cur.next = list2;
        }
        return dummy.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
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        // 新建了一个list
        ListNode mergedList = null;
        // for robustness
        if (list1 == null){
            return list2;
        }
        if (list2 == null){
            return list1;
        }
        
        if (list1.val <= list2.val){
            mergedList = list1;
            mergedList.next = Merge(list1.next, list2);
        } else {
            mergedList = list2;
            mergedList.next = Merge(list1, list2.next);
        }
        return mergedList;
    }
}

其他

插入

自己最开始的思路是，从list2中一个一个取结点插入到list1中。下一次的插入可以只从上一次插入结点遍历到list1的尾结点。但是搅了半天还是没有写出正确的代码。看到牛客网上有人给出的类似解答如下：

把list2往list1的中插。

  • 比较list2与list1的值：
    当list2值小等于list1值时往list1的前面插，并让list2指向下一个元素
    否则不进行插入，list1指向下一个结点。
  • 重复上述操作，直到有一个链表为空
  • 判断是哪个链表空了，如果是list2则说明list2已全部插入直接返回头结点即可。如果是list1，则将剩下的list2结点直接连到list1尾部，返回头结点即可。
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
链接：https://www.nowcoder.com/questionTerminal/d8b6b4358f774294a89de2a6ac4d9337?answerType=1&f=discussion
来源：牛客网

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1 == null ){
            return list2;
        }
        if(list2 == null){
            return list1;
        }
        if(list1 == null && list2 == null){
            return null;
        }
        //传入任意值初始化pre1，避免空指针异常。用于记录list1的前一个结点地址
        ListNode pre1 = new ListNode(-1);
        //用于记录list2的下一个结点地址
        ListNode p2 = null;
        //用于记录合并后链表的头结点。
        ListNode head = null;
        //如果list1的第一个结点值比list2第一个结点值小则用list1做表头
        if(list1.val < list2.val){
            head = list1;
        }else{
            //否则用list2做表头
            head = list2;
        }
        //当链表1和链表2都不为空时
        while(list1 != null && list2 != null){
            //如果list2的值小于等于list1则往list1前面插
            if(list2.val <= list1.val){
                p2 = list2.next;        //用p2保存list2的下一个结点
                list2.next = list1;     //把list2与list1相连
                pre1.next = list2;      //让list1的前一个结点指向list2
                pre1 = list2;           //此时list1的前一个结点变成list，更新pre1
                list2 = p2;             //list2指向下一个结点
            }else {                     //否则list1指向下一个结点
                pre1 = list1;          
                list1 = list1.next;
            }
        }
        if(list2 != null){              //插完需要判断list2是否还有值，将list2剩余值插入
            pre1.next = list2;
        }
        return head;
    }
}

递归优化

另外看到一个很优美的python题解：

1
2
3
4
5
6
7
def Merge(self, pHead1, pHead2):
    # write code here
    if pHead1 and pHead2:
        if pHead1.val > pHead2.val:
            pHead1, pHead2 = pHead2, pHead1
        pHead1.next = self.Merge(pHead1.next, pHead2)
    return pHead1 or pHead2

总结

  1. 类似于并归排序。
  2. null只能赋值给引用类型的对象，不能赋值给基本的数据类型，如int。

References

牛客网讨论与题解

《剑指offer》

浅谈Java中的对象和引用

Java 基础篇 - 类与对象 （对于引用类型和基本类型的参数传递讲得很清晰）