LeetCode第二十一题：合并两个有序链表

admin
学习
2024-03-11
66热度
0评论

题目来源：LeetCode第二十一题

1.题目描述

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

示例 1：

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

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

提示：

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

2.解题思路

解法一：迭代法

描述：创建一个哨兵（dummy）节点，这个节点的作用是简化在头部插入节点的操作，确保算法逻辑的统一性。同时，创建一个尾指针，它始终指向结果链表的最后一个节点。同时遍历两个链表，比较当前两个链表节点的值。将较小值的节点接到尾指针的后面，然后移动位置尾指针到它的下一个节点，同时也移动被选中（值较小）的链表的当前节点到下一个节点。如果两个链表长度不同，将未遍历完的链表的剩余部分接到结果链表的末尾。返回哨兵节点的下一个节点，即合并后的链表的头节点。
时间复杂度：O(n + m)。两个链表的长度分别为 n 和 m。在迭代过程中，每次循环比较两个链表中的节点，直到到达其中一个链表的末尾，因此最多进行 n + m 次比较。
空间复杂度：O(1)。
参考代码：

java版：

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 创建一个哨兵节点，方便在其后添加元素
        ListNode dummy = new ListNode(0);
        // 初始化一个指针，用于构建新链表
        ListNode current = dummy;
        // 当两个链表都不为空时，比较当前节点的值，选择较小的节点接到新链表上
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                current.next = list1;
                // 移动list1的指针
                list1 = list1.next;
            } else {
                current.next = list2;
                // 移动list2的指针
                list2 = list2.next;
            }
            // 移动构建新链表的指针
            current = current.next;
        }
        // 如果其中一个链表已经遍历完，将另一个链表的剩余部分链接到新链表的末尾
        current.next = (list1 != null) ? list1 : list2;
        // 哨兵节点的下一个节点是合并后链表的头节点
        return dummy.next;
    }
}

C++版：

class Solution {
public:
	ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
		ListNode dummy(0);
		ListNode* tail = &dummy;
		// 当两个链表都不为空时，比较当前节点的值，选择较小的节点接到新链表上
		while (list1 && list2) {
			if (list1->val < list2->val) {
				tail->next = list1;
				list1 = list1->next;
			}
			else {
				tail->next = list2;
				list2 = list2->next;
			}
			tail = tail->next;
		}

		// 直接将未结束的链表连接到合并链表的末尾
		tail->next = list1 ? list1 : list2;

		// 返回合并后的链表的头节点
		return dummy.next;
	}
};

C版：

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
	// 创建哨兵节点以简化插入操作
	struct ListNode dummy;
	dummy.next = NULL;
	struct ListNode* tail = &dummy;

	while (list1 && list2) {
		if (list1->val < list2->val) {
			tail->next = list1;
			list1 = list1->next;
		}
		else {
			tail->next = list2;
			list2 = list2->next;
		}
		tail = tail->next;
	}

	// 直接将未遍历完的链表连接到合并链表的末尾
	tail->next = list1 ? list1 : list2;

	return dummy.next;
}

解法二：递归

描述：如果任一链表为空，递归结束，返回非空链表。如果两个链表都为空，返回任意一个。比较两个链表当前头节点的值，选择较小值的节点作为合并后链表的当前节点。然后，将选中节点的next指向剩余部分合并后的链表，这一步通过递归调用实现。每一层递归返回当前应该连接的节点，直到所有节点都正确连接。
时间复杂度：O(n + m)。这里n和m分别代表两个链表的长度。
空间复杂度：O(n + m)。递归算法的空间复杂度主要由递归调用栈的深度决定。在最坏情况下，递归深度等于链表的长度之和。
参考代码：

java版：

class Solution {
        public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 终止条件：当任一链表为空时，直接返回另一链表
        if (list1 == null) {
            return list2;
        } else if (list2 == null) {
            return list1;
        }

        if (list1.val < list2.val) {
            // 如果list1的头节点值更小，则将list1的头节点作为合并链表的当前节点
            // 递归处理list1的下一个节点与list2的合并过程
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            // 如果list2的头节点值更小或相等，则将list2的头节点作为合并链表的当前节点
            // 递归处理list2的下一个节点与list1的合并过程
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}

C++版：

class Solution {
public:
	ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
		// 终止条件：当任一链表为空时，直接返回另一链表
		if (list1 == nullptr) {
			return list2;
		}
		else if (list2 == nullptr) {
			return list1;
		}

		if (list1->val < list2->val) {
			// 如果list1的头节点值更小，则将list1的头节点作为合并链表的当前节点
			// 递归处理list1的下一个节点与list2的合并过程
			list1->next = mergeTwoLists(list1->next, list2);
			return list1;
		}
		else {
			// 如果list2的头节点值更小或相等，则将list2的头节点作为合并链表的当前节点
			// 递归处理list2的下一个节点与list1的合并过程
			list2->next = mergeTwoLists(list1, list2->next);
			return list2;
		}
	}
};

C版：

struct ListNode* mergeTwoLists(struct ListNode* list1, struct 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;
	}
}