剑指Offer_16

发表于 | 分类于

题目

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

解题思路

就简单的拼凑两条链表，注意一些代码的细节，详见代码内注释
注意因为Java的对象都是引用类型，当一个实例对象引用了null，不要试图操作如下代码

1
2
3
4
5
ListNode header = new ListNode(-1);
ListNode node1 = new ListNode(1);
ListNode cur = header.next;	//此时的cur引用的是null
header.next = node1;		//header.next 与 cur 并无关系
System.out.println(cur.val);	//因此会抛出异常javaNullPointException
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) {
        if(list1 == null){
            return list2;
        }
        if(list2 == null){
            return list1;
        }
        
        ListNode header = new ListNode(-1);
        ListNode cur = header;	//将cur指向header节点
        
        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;
        }
        
        //拼接可能出现未遍历的剩余节点
        cur.next = (list1 == null) ? list2 : list1;
        
        return header.next;
    }
}