本文共 1644 字，大约阅读时间需要 5 分钟。

合并两个排序的链表

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

思路

递归

public ListNode Merge(ListNode list1,ListNode list2) {        if(list1 == null) return list2;        if(list2 == null) return list1;        if(list1.val<=list2.val){            list1.next = Merge(list1.next,list2);            return list1;        }else{            list2.next = Merge(list1,list2.next);            return list2;        }    }

非递归
在while循环中比较两个链表指针所在位置的值，将较小的链接到新的链表中

public ListNode Merge(ListNode list1,ListNode list2) {        if(list1 == null) return list2;        if(list2 == null) return list1;        ListNode node = null;        ListNode temp = null;        while(list1!=null&&list2!=null){            if(list1.val<=list2.val){ //链接之后怎么保证                if(node == null){                    node = temp = list1;                }else{                    temp.next = list1;                     temp = temp.next;                }                list1 = list1.next;            }else{                if(node == null){                    node = temp = list2;                }else{                    temp.next = list2;                    temp = temp.next;                }                list2 = list2.next;            }        }        if(list1==null) temp.next = list2;        else temp.next = list1;        return node;    }

突破点
1、指针问题
ListNode node = null;
ListNode temp = null;
temp = node;
node = new ListNode(1);
System.out.println(temp.val);
会出现空指针异常，此处temp并不是指针，所以赋值的时候也需要给temp赋值，才能使用temp

2、不需要创建节点
temp.next = list1;
temp = temp.next;
直接把节点赋值过去就可以了

3、可以直接对头节点判断是否为空

if(node == null){	node = temp = list1;	}else{		temp.next = list1; 		temp = temp.next;	}}