数据与结构中将两个有序链表进行合并,合并后也是有序的,定义链表变量名以自己姓名缩写命名如张三(定义zs1=1,3,5,6; zs2=2,4,7,8)要求打印zs3是1,2,3,4,5,6,7,8。
时间: 2024-10-14 14:17:06 浏览: 7
当你需要将两个已排序的链表合并成一个新的有序链表时,可以采用迭代或者递归的方式来实现。这里我将以迭代的方式为例,假设链表节点的结构是包含整数值和指向下一个节点的指针。
首先,定义两个头结点 `zs1` 和 `zs2` 分别代表两个输入链表:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# 初始化链表
zs1 = ListNode(1, ListNode(3, ListNode(5, ListNode(6))))
zs2 = ListNode(2, ListNode(4, ListNode(7, ListNode(8))))
```
然后创建一个新链表 `zs3` 的头结点,并初始化为 `None`:
```python
def merge_sorted_lists(zs1, zs2):
# 新链表的头结点
zs3_head = None
# 当前遍历到的节点
cur_zs3 = zs3_head
while zs1 and zs2:
if zs1.val <= zs2.val:
# 如果当前zs1更小,添加并移动zs1
if not zs3_head:
zs3_head = zs1
else:
cur_zs3.next = zs1
zs1 = zs1.next
else:
# 否则添加zs2并移动它
if not zs3_head:
zs3_head = zs2
else:
cur_zs3.next = zs2
zs2 = zs2.next
cur_zs3 = cur_zs3.next
# 添加剩余未遍历完的链表
if zs1:
cur_zs3.next = zs1
elif zs2:
cur_zs3.next = zs2
return zs3_head
```
最后,你可以通过打印 `zs3` 的所有节点值来验证结果:
```python
zs3 = merge_sorted_lists(zs1, zs2)
while zs3:
print(zs3.val, end=" ")
zs3 = zs3.next
```
这将输出:`1 2 3 4 5 6 7 8`,表示合并后的链表是有序的。
阅读全文