题解 | #合并两个排序的链表#

/*
public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}*/
/**
思路解析：(前提是两个链表均是有序的)
1.首先对于特殊情况的链表做出判断，如果其中一个为空，那么两表合并必为其中一个的原链表
2.创建新链表，用于保存两个链表的结合，设置为以head节点开头，后期用于返回合并链表的头节点，在这里使用cur保存head节点，为的是用于两表合并应该存放在新链表的位置
3.核心代码逻辑部分，只要两个链表不为空，那么就一直遍历，在循环中做出判断，两个链表的当前头节点val部分值的大小，小的优先放进新链表中，待不满足条件(比如其中一个链表的节点为null了)，就跳出循环
4.做一些收尾操作，比如有一个链表的节点不为null，那么我们就要将剩余的节点与我们新的链表做一个指针的引用，指向旧链表当前节点的位置
*/
public class Solution {
    public ListNode Merge(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
	  //-------------------------以上为第一部分--------------------------------------
        ListNode head = new ListNode(0);
        ListNode cur = head;
	  //-------------------------以上为第二部分--------------------------------------
        while (list1 != null && list2 != null) {
            if (list1.val > list2.val) {
                cur.next = list2;
                list2 = list2.next;
            } else {
                cur.next = list1;
                list1 = list1.next;
            }
            cur = cur.next;
        }
	  //-------------------------以上为第三部分--------------------------------------
        if (list1 != null) {
            cur.next = list1;
        } else {
            cur.next = list2;
        }
	  //-------------------------以上为第四部分--------------------------------------
        return head.next; //返回头节点的下一个节点是因为我们使用的节点确实是从head的下一个节点开始的
    }
}