算法

010 链表入门题-力扣21-合并两个升序链表

这篇博客讲解了如何合并两个升序链表（LeetCode 21）。提供了递归和非递归两种解法。递归解法简洁，通过比较头节点大小，递归合并剩余部分。非递归解法则通过迭代，使用 pre 指针连接较小节点，最终合并两个链表。链表题能有效考察编码能力。

Posted by Hilda on March 20, 2025

概览：

前置知识：理解链表及其基本调整

建议：做过这个题的同学跳过

将两个升序链表合并为一个新的升序链表并返回

新链表是通过拼接给定的两个链表的所有节点组成的

链表题目在笔试、面试中的意义就是检验coding能力如何

更难的题目会在【必备】课程里讲述

测试链接 : https://leetcode.cn/problems/merge-two-sorted-lists/

21. 合并两个有序链表

21. 合并两个有序链表

解法1:递归

/**
 * 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) {
        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;
        }
    }
}

解法2:非递归

/**
 * 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 static ListNode mergeTwoLists(ListNode head1, ListNode head2) {
        if (head1 == null || head2 == null) {
            return head1 == null ? head2 : head1;
        }
        ListNode head = head1.val <= head2.val ? head1 : head2;
        ListNode cur1 = head.next;
        ListNode cur2 = head == head1 ? head2 : head1;
        ListNode pre = head;
        while (cur1 != null && cur2 != null) {
            if (cur1.val <= cur2.val) {
                pre.next = cur1;
                cur1 = cur1.next;
            } else {
                pre.next = cur2;
                cur2 = cur2.next;
            }
            pre = pre.next;
        }
        pre.next = cur1 != null ? cur1 : cur2;
        return head;
    }
}