[数据结构与算法]有序链表合并

问题

两个有序的链表按照从小到大合并

思路

1.找出头节点小的链表作为最终返回的起始节点
2.两个节点分别指向小头的下一个节点，以及大头的头节点
3.定义pre指针，作为指向当前节点的指针
4.比较2中两个节点的大小，让pre指针指向这个节点，并让这个节点向后移动，循环往复。
5.最终当任何一个链表的next为空了，则pre的next指向不为空的链表，结束返回。

代码实现

    public static ListNode mergeTwoListNode(ListNode node1,ListNode node2){
        // 只要有一个为空就返回不为空的。
        if (node1 == null || node2 == null){
            return node1 == null ? node2 :node1;
        }
        // 找到头节点小的链表记为要返回的head。
        ListNode head = node1.value <= node2.value ? node1 : node2;
        // 记录小头链表的下一个节点。
        ListNode cur1 = head.next;
        // 记录大头节点的下一个节点。
        ListNode cur2 = head == node1 ? node2 : node1;
        // 记录移动指针。
        ListNode pre  = head;
        // 只要有一个链表为空了则跳出循环。
        while (cur1 != null && cur2 != null){
            // pre指向下一个小节点。
            if (cur1.value <= cur2.value){
                pre.next = cur1;
                cur1 = cur1.next;
            }else {
                pre.next = cur2;
                cur2 = cur2.next;
            }
            // 移动pre。
            pre = pre.next;
        }
        // 当一个链表为空了，另外一个链表还有值的情况下直接指向。
        pre.next = cur1 == null ? cur2 : cur1;
        // 返回
        return head;
    }