合并链表代码
时间: 2023-07-02 11:13:16 浏览: 47
合并两个有序链表的代码如下所示:
```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(-1)
prev = dummy
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
prev.next = l1 if l1 else l2
return dummy.next
```
其中,我们使用了一个哑结点(dummy)来简化代码实现。在循环中,我们判断当前两个链表头结点的值,将较小的结点接到prev指针后面,然后将该链表头结点指针后移,继续比较,直到其中一个链表为空。最后,将剩余的链表接到合并链表的末尾即可。
注意,该代码实现的时间复杂度为$O(m+n)$,其中m和n分别为两个链表的长度。
相关问题
python合并链表
要在Python中合并链表,有两种常见的情况:
1. 直接合并,没有什么规则,只是将多个链表的头尾相连合并成一个链表。例如,可以使用以下代码实现直接合并多个链表:
```python
from slinklist import SlinkList
def concat(lista):
slink = SlinkList()
for ll in lista:
sllv = ll.display()
for v in sllv:
slink.appendtail(v)
return slink
def main():
sll1 = SlinkList()
sll2 = SlinkList()
for i in range(1, 6):
sll1.appendtail(i)
sll2.appendtail(i * i)
lst = [sll1, sll2]
newlinklist = concat(lst)
print(newlinklist.display())
#### 引用[.reference_title]
- *1* *2* *3* [Python——数据结构——链表——合并单链表](https://blog.csdn.net/qq_41188247/article/details/122128989)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v92^chatsearchT0_1"}}] [.reference_item style="max-width: 100%"]
[ .reference_list ]
头插法合并有序链表代码
以下是头插法合并有序链表的代码:
```
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode(0);
ListNode* cur = dummy;
while (l1 && 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 ? l1 : l2;
return dummy->next;
}
```
希望能够帮到你!