21.合并两个有序链表

我的思路：用双指针，类似归并排序的思想

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def mergeTwoLists(self, list1, list2):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        # 检查两个链表是否都为空
        if not list1 and not list2:
            return None
        # 如果其中一个链表为空，则返回另一个链表
        if not list1 and list2: #list1是空的
            return list2
        if list1 and not list2: #list2是空的
            return list1

        # 初始化指针p和q，并选择头节点
        p = list1
        q = list2
        if p.val <= q.val:
            head = p
        else:
            head = q

        # 合并两个链表
        while p and q:
            if p.val <= q.val:
                temp1 = p.next
                p.next = q
                p = temp1
            else:
                temp2 = q.next
                q.next = p
                q = temp2

        return head

代码错误：
①通过索引 list1[0]和list2[0]访问链表元素是不正确的，因为list1和list2不是列表，而是ListNode对象。
②代码中没有正确更新头节点head的机制，使得最终返回的头节点可能不正确。
③在while循环中的逻辑有误，我在循环中尝试在两个链表之间进行节点交换，但处理不完整，且缺少正确的节点连接操作，导致结果不正确。
ChatGPT修改后版本：

class Solution(object):
    def mergeTwoLists(self, list1, list2):
        # 检查其中一个链表是否为空
        if not list1:
            return list2
        if not list2:
            return list1

        # 初始化指针和虚拟头节点
        dummy = ListNode(0)  # 创建一个虚拟头节点
        current = dummy  # current指向虚拟头节点
        p = list1  # 指针p指向链表list1的头部
        q = list2  # 指针q指向链表list2的头部

        # 遍历两个链表并合并它们
        while p and q:
            if p.val <= q.val:  # 如果p节点的值小于等于q节点的值
                current.next = p  # 当前节点的下一个节点指向p节点
                p = p.next  # 移动p指针到下一个节点
            else:  # 如果q节点的值小于p节点的值
                current.next = q  # 当前节点的下一个节点指向q节点
                q = q.next  # 移动q指针到下一个节点
            current = current.next  # 移动当前节点到下一个节点

        # 将非空链表的剩余节点连接到合并后的链表
        if p:  # 如果链表list1还有剩余节点
            current.next = p  # 将current的下一个节点连接到p链表的剩余部分
        if q:  # 如果链表list2还有剩余节点
            current.next = q  # 将current的下一个节点连接到q链表的剩余部分

        return dummy.next  # 返回虚拟头节点的下一个节点，即合并后链表的头节点

用时和内存

方法一、迭代
思路基本同上述ChatGPT修改后的。

思路和算法

class Solution:
    def mergeTwoLists(self, l1, l2):
        prehead = ListNode(-1)

        prev = prehead
        while l1 and l2:
            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 if l1 is not None else l2

        return prehead.next

用时和内存

时间复杂度：O(n+m)，其中n和m分别为两个链表的长度。因为每次循环迭代中，l1 和 l2 只有一个元素会被放进合并链表中， 因此 while 循环的次数不会超过两个链表的长度之和。所有其他操作的时间复杂度都是常数级别的，因此总的时间复杂度为 O(n+m)。
空间复杂度：O(1)。只需要常数的空间存放若干变量。

方法二、递归

思路和算法

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def mergeTwoLists(self, list1, list2):
        if list1 is None:
            return list2
        elif list2 is None:
            return list1
        elif list1.val <= list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1, list2.next)
            return list2

用时和内存

时间复杂度：O(n+m)，其中n和m分别为两个链表的长度。因为每次调用递归都会去掉l1或者l2的头节点（直到至少有一个链表为空），函数 mergeTwoList 至多只会递归调用每个节点一次。因此，时间复杂度取决于合并后的链表长度，即O(n+m)。
空间复杂度：O(n+m)，其中n和m分别为两个链表的长度。递归调用mergeTwoLists函数时需要消耗栈空间，栈空间的大小取决于递归调用的深度。结束递归调用时mergeTwoLists函数最多调用n+m次，因此空间复杂度为O(n+m)。