如何创建两个有序链表
时间: 2024-09-21 19:10:38 浏览: 23
创建两个有序链表通常涉及以下几个步骤:
1. **初始化**:首先,你需要为每个链表创建节点。每个节点包含两个部分:数据值和指向下一个节点的指针。你可以手动创建这些节点,也可以通过循环来动态生成。
```python
# Python示例
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
list1_head = ListNode(1) # 链表1的第一个节点,值为1
list1_head.next = ListNode(3) # 链表1的第二个节点,值为3
list1_head.next.next = ListNode(5) # 链表1的第三个节点,值为5
list2_head = ListNode(2) # 链表2的第一个节点,值为2
list2_head.next = ListNode(4) # 链表2的第二个节点,值为4
list2_head.next.next = ListNode(6) # 链表2的第三个节点,值为6
```
2. **合并**:如果两个链表都有多个节点,你需要将它们按照数值大小进行比较,较小的节点添加到新的链表中,然后继续比较直到遍历完其中一个链表。当一个链表遍历完毕,将另一个链表剩下的部分直接添加到新链表的末尾。
```python
def merge_sorted_lists(list1_head, list2_head):
merged_head = None # 新链表的头节点
if not list1_head or not list2_head:
return list1_head if list1_head else list2_head
if list1_head.val < list2_head.val:
merged_head = list1_head
list1_head = list1_head.next
else:
merged_head = list2_head
list2_head = list2_head.next
current = merged_head
while list1_head and list2_head:
if list1_head.val < list2_head.val:
current.next = list1_head
list1_head = list1_head.next
else:
current.next = list2_head
list2_head = list2_head.next
current = current.next
# 将剩余的部分添加到新链表
if list1_head:
current.next = list1_head
elif list2_head:
current.next = list2_head
return merged_head
```
阅读全文