【LeetCode】3. Merge Two Sorted Lists·合并两个有序链表

题目描述

英文版描述

You are given the heads of two sorted linked lists list1 and list2. Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists. Return the head of the merged linked list.

英文版地址

https://leetcode.com/problems/merge-two-sorted-lists/https://leetcode.com/problems/merge-two-sorted-lists/

中文版描述

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]

输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []

输出：[]

示例 3：

输入：l1 = [], l2 = [0]

输出：[0]

Constraints·提示：

• 两个链表的节点数目范围是 [0, 50]

• -100 <= Node.val <= 100

• l1 和 l2 均按 非递减顺序 排列

中文版地址

https://leetcode.cn/problems/merge-two-sorted-lists/https://leetcode.cn/problems/merge-two-sorted-lists/

解题思路

我的第一反应就是全部读取，然后一个一个比较，再放进一个新的链表里，后来又想了想，这两个输入的链表是已经排好序的，那么其实可以从分别从两个链表读取数据做比较，小的那个存进新的链表并指向该链表的下一个数据，大的继续跟这个新数据做比较……如此重复，直到有一个链表空了，把未空的链表剩余的数据加在新链表尾部，返回新链表即可。

解题方法

俺这版

递归法

  public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        else if (list2 == null) {
            return list1;
        }
        else if (list1.val <= list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
  
  //    Definition for singly-linked list.

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

​

官方版

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode prehead = new ListNode(-1);

        ListNode prev = prehead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }

        // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev.next = l1 == null ? l2 : l1;

        return prehead.next;
    }
    
 //    Definition for singly-linked list.

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

欢迎有更好方法的同学同学评论区踢我(｡･ω･｡)ﾉ