有两个有序链表A和B,A中存放的是1 ,3,5,7,9。 B中存放的是2,4,6,8,10. 要求将两个有序链表合成一个有序链表1,2,3,4,5,6,7,8,9,10
时间: 2023-09-07 17:13:41 浏览: 119
好的,这是一道经典的链表合并问题。可以使用双指针法,将两个链表的节点值依次比较,将较小的节点插入到新链表中,直到其中一个链表为空,再将另一个链表中剩余的节点依次插入到新链表中即可。
以下是具体的代码实现:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode()
cur = dummy
while l1 and l2:
if l1.val < l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
cur.next = l1 if l1 else l2
return dummy.next
```
其中,dummy节点是为了方便处理而创建的虚拟头节点,cur指针指向新链表的最后一个节点,初始时指向dummy节点。while循环中,每次比较l1和l2的节点值,将较小的节点插入到新链表中,并将cur指针指向该节点。最后,如果其中一个链表还有剩余节点,直接将其添加到新链表的末尾即可。
阅读全文