当前位置：首页 > ds >正文

力扣热题100之合并两个有序链表

ds 2025/5/14 9:10:33

题目

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
在这里插入图片描述

代码

方法一：新建一个链表

这里就先随便新建一个节点作为一个链表的头节点，然后每次遍历都将小的那个节点放入这个链表，遍历完一个链表之后，将另一个链表后面的所有数都接在这个新链表后面，输出的时候从这个新链表的第二个节点开始输出。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:res=ListNode(1)#新链表prev = reswhile list1 and list2:if list1.val<=list2.val:prev.next=list1list1=list1.nextelse:prev.next=list2list2=list2.nextprev=prev.nextprev.next=list1 if list1 != None else list2return res.next

方法二：递归

只能说这个方法太强了，过程大概就像下面这个图这样
在这里插入图片描述

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:if not list1:return list2if not list2:return list1if list1.val<list2.val:list1.next=self.mergeTwoLists(list1.next,list2)return list1else:list2.next=self.mergeTwoLists(list1,list2.next)return list2