原题链接：https://leetcode.cn/problems/merge-two-sorted-lists/

解题要点：

  • 使用一个虚拟节点指向刚开始处（因为此时并不知道新链表的头节点在哪儿）

  • 构造一个pre节点，用来构造新的链表。在遍历两个链表的时候，发现哪个链表节点值较小，就将pre节点的next指向该链表节点，同时将该链表往前移动一步。在每次比较完值之后， 将pre也往前移动一步，这样新的链表节点也就在不断的产生了

  • 在遍历结束之后，可能会存在某个链表还没有遍历完，此时直接将其链接到pre即可

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
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 虚拟节点, next指针为null， 因为此时不知道list1和list2的头结点谁更小
        ListNode virtual = new ListNode(-1, null);
   
        ListNode pre = virtual;

        while (list1 != null && list2 != null){
            if (list1.val < list2.val){
                pre.next = list1;
                list1 = list1.next;
            } else {
                pre.next = list2;
                list2 = list2.next;
            }
            pre = pre.next;
        }
        if (list1 != null){
            pre.next = list1;
        }
        if (list2 != null){
            pre.next = list2;
        }
    	// virtual.next指向了新链表的头节点
        return virtual.next;
    }