假设有两个按元素值递增次序排列的线性表,均以单链表形式存储。请编写法将这两个单链表归并为一个按元素值递减次序排列的单链表,并要求利用原来两个单链表的结点存放归并后的单链表。
时间: 2024-10-12 15:14:51 浏览: 56
要合并两个按元素值递增排序的单链表,得到一个按元素值递减排序的新链表,同时保持原有的节点结构,可以采用以下步骤:
1. 创建一个新的头节点`newHead`,用于存放合并后的链表。
2. 初始化两个指针`p1`和`p2`分别指向两个输入链表的头部。
3. 当`p1`和`p2`都不为空时,比较它们当前节点的值。取较小的节点(即当前元素较大的那个),将其添加到新链表`newHead`的后面,并移动该节点到原链表的下一个节点。如果`p1`的值小于`p2`,则更新`p1`;反之,更新`p2`。
4. 当其中一个指针到达链表末尾时,将另一个剩余的链表剩余部分直接接到新链表的尾部。
5. 最终,返回新的头节点`newHead`,它就是按照元素值递减顺序排列的合并链表。
以下是这个过程的伪代码示例:
```python
def merge_sorted_lists(list1_head, list2_head):
new_head = ListNode(0) # 创建新链表的头节点
current = new_head
while p1 and p2:
if p1.val > p2.val: # 如果p1的值较大,选择p2并链接
current.next = p2
p2 = p2.next
else: # 否则选择p1并链接
current.next = p1
p1 = p1.next
if p1: # 将未遍历完的链表连接到新链表末尾
current.next = p1
elif p2: # 同理处理第二个链表
current.next = p2
return new_head
```
阅读全文