关于leetcode:leetcode-21-Merge-Two-Sorted-Lists-合并两个有序链表简单

1次阅读

共计 1203 个字符，预计需要花费 4 分钟才能阅读完成。

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

示例 1：

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

示例 2：

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

示例 3：

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

提醒：

两个链表的节点数目范畴是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按非递加程序排列

起源：力扣（LeetCode）
链接：https://leetcode.cn/problems/…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

还是分递归和迭代两种思路来实现，要了解链表

/**
 * 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;}
 * }
 */
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 提示信息：// 两个链表的节点数目范畴是 [0, 50]
        // -100 <= Node.val <= 100
        // l1 和 l2 均按 非递加程序 排列
        if (list1 == null) {return list2;}
        if (list2 == null) {return list1;}
        if (list1.val > list2.val) {list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
        list1.next = mergeTwoLists(list1.next, list2);
        return list1;
    }
}

class Solution2 {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode ans = new ListNode(0);
        ListNode cursor = ans;
        while (list1 != null && list2 != null) {if (list1.val <= list2.val) {
                cursor.next = list1;
                list1 = list1.next;
            } else {
                cursor.next = list2;
                list2 = list2.next;
            }
            cursor = cursor.next;
        }
        cursor.next = list1 != null ? list1 : list2;
        return ans.next;
    }
}