《链表篇》---合并两个有序链表

用户11288958

发布于 2025-05-31 14:52:53

1630

文章被收录于专栏：学习学习

题目传送门

方法一：迭代

1.定义一个新的节点。 2.同时遍历两个链表的值。若链表1的值小于链表2。则新节点链接链表1。并链表1往后走一位。反之链接链表2。链表2往后走一位。最后创建的新的链表节点也往后走一位。 3.在链表1和链表2都不为空的情况下。重复2的步骤。直到某一个链表遍历完毕。 4.最后拼接尚未遍历完的链表。 5.返回新建链表。

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(0);
        ListNode prev = dummy;

        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                prev.next = list1;
                list1 = list1.next;
            }else{
                prev.next = list2;
                list2 = list2.next;
            }
            prev = prev.next;
        }
        // 连接剩余的链表
        prev.next = list1 != null ? list1 : list2;
        return dummy.next;
    }
}

复杂度分析：

方法二：递归

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

        if(list1 == null){
            return list2;
        }
        if(list2 == null){
            return list1;
        }

        if(list1.val <= list2.val){
            list1.next = mergeTwoLists(list1.next,list2);
            return list1;
        }else{
            list2.next = mergeTwoLists(list1,list2.next);
            return list2;
        }
    }
}