[数据结构与算法]剑指Offer - 16_合并两个排序的链表

题目描述

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

思路

1. 因为两个链表是有序的，所以同时遍历两个链表，找到值小的一个放到结果链表的最后，然后再让值小的结点指向后继节点
2. 依次类推，直到其中一个链表遍历结束，则剩余的链表的值肯定都大于等于结果链表的最后一个节点的值
3. 就直接把剩余链表添加到结果链表的最后
4. 最后返回结果链表的头节点即可

Code

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(-1);
        ListNode tempHead = head;
        //只要有一个链表遍历结束则终止
        while (l1 != null && l2 != null) {
            //tempHead的后继结点为l1、l2中小的一个
            //小的一个再指向其后继节点
            int val1 = l1.val;
            int val2 = l2.val;
            if (val1 <= val2) {
                tempHead.next = new ListNode(val1);
                l1 = l1.next;
            } else {
                tempHead.next = new ListNode(val2);
                l2 = l2.next;
            }
            //tempHead指向其后继节点
            tempHead = tempHead.next;
        }
        //最后哪一个没遍历完，就是tempHead的后继节点
        tempHead.next = l1 == null ? l2 : l1;
        //最后返回head的后继节点即可
        return head.next;
    }
}