用LinkList类型自行建立两个有序的单链表,其中使用头插法创建链表 La,使用尾插法创建链表 Lb。将 La 与 Lb合并,得到有序链表 Lc
时间: 2024-10-29 14:13:11 浏览: 7
在Python中,我们可以首先定义一个链表节点类`ListNode`,然后分别用头插法(head insert)和尾插法(tail append)创建两个链表La和Lb。最后,通过比较节点值,合并这两个链表成一个新的有序链表Lc。
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def build_sorted_list(head, values):
if not head:
return ListNode(values[0])
current = head
for value in values:
new_node = ListNode(value)
if current.val > value:
new_node.next = current
current = new_node
else:
while current.next and current.next.val < value:
current = current.next
current.next = new_node
return head
# 创建头插法链表La
values_la = [1, 3, 5, 7]
la_head = None
for value in values_la:
la_head = build_sorted_list(la_head, [value])
# 创建尾插法链表Lb
values_lb = [2, 4, 6, 8]
lb_tail = None
for value in values_lb:
lb_tail = build_sorted_list(build_sorted_list(lb_tail, [value]), [value])
# 合并两个链表Lc
lc_head = la_head
while lc_head and lb_tail:
if lc_head.val <= lb_tail.val:
lc_head.next = lb_tail
if lb_tail.next:
lb_tail = lb_tail.next
else:
break
else:
lc_head = lc_head.next
if lb_tail:
lc_head.next = lb_tail
# 输出合并后的链表Lc
current = lc_head
while current:
print(current.val, end=" -> ")
current = current.next
print("None")
阅读全文