2021/1/17 合并有序链表

1 解题思路

1. 声明两个指针ptr和mark，mark用于标记其中一个链表的位置，ptr用于游走在另一个链表和mark上的ListNode进行比较。
2. 将ptr定义为表头value值较小的链表，mark定义为另一个链表的表头。
3. ptr开始向后游走，若遇到比mark小的value，ptr继续向后游走，否则将mark所在的ListNode嵌入ptr所在的链表中，mark则向后移动一位。
   如图所示：
   

   2 Java代码实现

注：实际代码操作与上图有所出入，图片中的ptr在代码里是ptr.next

public class Solution {

    ListNode ptr;
    ListNode mark;
    ListNode newListNode;

    public ListNode mergeTwoLists (ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        else if (l2 == null) return l1;
        // write code here
        ptr = l1.val < l2.val ? l1 : l2;
        mark = l1.val >= l2.val ? l1 : l2;
        newListNode = ptr;
        // 比较两个链表，链表1当前节点的下一个节点数值比链表2的大，则链表2的当前节点变为链表1的下一个节点
        // 且链表2被抽取的节点的下一个节点变为链表1的下下个节点
        while (ptr.next != null) {
            // 如果被取的一方已空，直接返回
            if (mark == null) return newListNode;
            if (ptr.next.val > mark.val) {
                ListNode temp = mark.next;
                mark.next = ptr.next;
                ptr.next = mark;
                mark = temp;
            }
            ptr = ptr.next;
        }
        ptr.next = mark;
        return newListNode;
    }
}