分别采用尾插入法创建两个有序的单链表:LA, LB;然后将这两个单链表并为一个有序的单链表LC。
时间: 2024-02-27 10:51:45 浏览: 16
好的,我会为您解答这个问题。
首先,我们需要先创建两个有序的单链表 LA 和 LB。采用尾插入法,可以较为方便地实现。
以 LA 为例,我们可以定义一个头结点,然后依次读入 LA 中的元素,将它们插入到头结点之后。在插入的过程中,需要保证新插入的元素仍然保持有序。
具体的代码实现如下:
```python
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def createList():
head = ListNode(None)
tail = head
nums = input("请输入有序单链表(以空格分隔):").split()
for num in nums:
node = ListNode(int(num))
tail.next = node
tail = node
return head.next
```
类似的,我们也可以创建 LB。
接下来,我们需要将 LA 和 LB 合并成一个有序的单链表 LC。同样地,我们可以定义一个头结点,然后依次比较 LA 和 LB 中的元素,将它们按照大小顺序插入到头结点之后。
具体的代码实现如下:
```python
def mergeList(head1, head2):
head = ListNode(None)
tail = head
p1, p2 = head1, head2
while p1 and p2:
if p1.val < p2.val:
tail.next = p1
p1 = p1.next
else:
tail.next = p2
p2 = p2.next
tail = tail.next
if p1:
tail.next = p1
if p2:
tail.next = p2
return head.next
```
最后,我们可以调用上述代码,分别创建 LA 和 LB,然后将它们合并为 LC。
完整的代码如下:
```python
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def createList():
head = ListNode(None)
tail = head
nums = input("请输入有序单链表(以空格分隔):").split()
for num in nums:
node = ListNode(int(num))
tail.next = node
tail = node
return head.next
def mergeList(head1, head2):
head = ListNode(None)
tail = head
p1, p2 = head1, head2
while p1 and p2:
if p1.val < p2.val:
tail.next = p1
p1 = p1.next
else:
tail.next = p2
p2 = p2.next
tail = tail.next
if p1:
tail.next = p1
if p2:
tail.next = p2
return head.next
if __name__ == '__main__':
LA = createList()
LB = createList()
LC = mergeList(LA, LB)
print("LA: ", end="")
p = LA
while p:
print(p.val, end=" ")
p = p.next
print()
print("LB: ", end="")
p = LB
while p:
print(p.val, end=" ")
p = p.next
print()
print("LC: ", end="")
p = LC
while p:
print(p.val, end=" ")
p = p.next
print()
```
希望能够帮助到您!