首页合并两个有序单链表并逆序输出代码

合并两个有序单链表并逆序输出代码

时间: 2024-12-02 11:18:53 浏览: 44

合并两个有序单链表并将结果逆序后输出，可以分为两步操作：第一步，合并两个有序链表。这通常通过比较两个链表当前节点的值，并将较小的那个节点添加到新链表中，直到其中一个链表遍历完。第二步，反转这个新的合并链表。你可以创建一个新的头结点，然后遍历链表，每次将当前节点的下一个节点赋给当前节点，最后返回新头结点。下面是一个Python示例，假设`ListNode`是链表节点类，包含`val`和`next`属性： ```python class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def merge_sorted_lists(l1, l2): # Step 1: Merge two sorted lists if not l1: return l2 elif not l2: return l1 elif l1.val < l2.val: l1.next = merge_sorted_lists(l1.next, l2) return l1 else: l2.next = merge_sorted_lists(l1, l2.next) return l2 def reverse_list(head): prev = None current = head while current: next_temp = current.next current.next = prev prev = current current = next_temp return prev # 使用例子 l1 = ListNode(1, ListNode(2, ListNode(4))) l2 = ListNode(1, ListNode(3, ListNode(4))) merged_and_reversed = reverse_list(merge_sorted_lists(l1, l2)) while merged_and_reversed: print(merged_and_reversed.val, end=" ") merged_and_reversed = merged_and_reversed.next ``` 在这个例子中，先合并了`l1`和`l2`，然后将结果反转后依次输出每个节点的值。

阅读全文