[数据结构与算法]21.合并两个有序链表

leetcode原题链接

题目描述：

解法：模拟

声明一个 dumpnode（哨兵节点）用于返回最终的链表。
ListNode temp = dumpnode;
比较 list1 和 list2 的 val。

while(list1 != null && list2 != null){
	if(list1.val < list2.val) {
		temp.next = list1;
		list1 = list.next;
		temp.next = null; // 此处截断temp 后面的。
	} else {
		... // 同上
	}
}

最后判断一下list1 或 list2 后面是否还有节点。

if(list1 != null){
	temp.next = list1
}
if(list2 != null){
	temp.next = list2;
}

代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

        ListNode dumpnode = new ListNode(0, null);
        ListNode temp = dumpnode;
        while(list1 != null && list2 != null){
            if(list1.val < list2.val){
                temp.next = list1;
                list1 = list1.next;
            } else {
                temp.next = list2;
                list2 = list2.next;
            }
            temp = temp.next;
            temp.next = null;
        }
    
        if(list1 != null){
            temp.next = list1;
        }
        if(list2 != null){
            temp.next = list2;
        }
        
        return dumpnode.next;
    }
}