将两个链表合并为一个链表的算法可以使用迭代或递归方法。
方法1:迭代 迭代方法通过比较两个链表的节点值,将较小的节点依次加入到新链表中。具体步骤如下:
具体代码如下(使用Python语言):
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode(0) # 创建结果链表的头部
curr = dummy # 当前结果链表的指针
while l1 and l2: # 迭代直到两个链表都遍历完
if l1.val < l2.val:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next
curr = curr.next
# 将剩余的链表连接到结果链表的末尾
curr.next = l1 if l1 else l2
return dummy.next # 返回结果链表的头部
方法2:递归 递归方法通过不断比较两个链表的头节点,将较小的节点加入到结果链表中,并递归地处理剩下的节点。具体步骤如下:
具体代码如下(使用Python语言):
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
if not l1:
return l2
if not l2:
return l1
if l1.val < l2.val:
l1.next = mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = mergeTwoLists(l1, l2.next)
return l2
这两种方法都可以实现将两个链表合并为一个链表的功能。它们的时间复杂度都是O(n + m),其中n和m分别为两个链表的长度。
领取专属 10元无门槛券
手把手带您无忧上云