合并两个有序链表python创建实例

### 创建与合并两个有序链表 在 Python 中，可以通过定义 `ListNode` 类来表示链表节点，并利用迭代或递归的方式实现两个有序链表的合并。 #### 定义 ListNode 类 为了构建链表，首先需要定义一个简单的 `ListNode` 类： ```python class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next ``` 此段代码定义了链表节点的数据结构[^4]。 #### 迭代法实现合并 迭代方法通过引入哨兵节点简化边界条件处理过程。具体做法如下所示： ```python def mergeTwoLists_iteratively(l1, l2): prehead = ListNode(-1) prev = prehead while l1 and l2: if l1.val <= l2.val: prev.next = l1 l1 = l1.next else: prev.next = l2 l2 = l2.next prev = prev.next # 合并剩余部分 prev.next = l1 if l1 is not None else l2 return prehead.next ``` 这段程序展示了如何使用迭代方式高效地完成两者的融合工作[^1]。 #### 递归法实现合并 对于递归版本，则是基于分治的思想逐步缩小问题规模直至最小子问题可以直接解决为止： ```python def mergeTwoLists_recursively(l1, l2): if not l1 or not l2: return l1 or l2 if l1.val < l2.val: l1.next = mergeTwoLists_recursively(l1.next, l2) return l1 else: l2.next = mergeTwoLists_recursively(l1, l2.next) return l2 ``` 上述逻辑清晰表达了递归调用过程中每次只关注当前最小元素的选择及其后续链接关系建立的过程[^3]。 #### 测试案例 下面给出一组测试样例用于验证上述两种不同策略的有效性和正确性： ```python if __name__ == "__main__": # 构建第一个链表: 1->2->4 list1_node1 = ListNode(1) list1_node2 = ListNode(2) list1_node4 = ListNode(4) list1_node1.next = list1_node2 list1_node2.next = list1_node4 # 构建第二个链表: 1->3->4 list2_node1 = ListNode(1) list2_node3 = ListNode(3) list2_node4 = ListNode(4) list2_node1.next = list2_node3 list2_node3.next = list2_node4 merged_list_iterative = mergeTwoLists_iteratively(list1_node1, list2_node1) merged_list_recursive = mergeTwoLists_recursively(list1_node1, list2_node1) current_node = merged_list_iterative result_str = "" while current_node != None: result_str += str(current_node.val) + "->" current_node = current_node.next print(result_str[:-2]) # 输出不带最后一个箭头的结果串 ``` 该片段不仅实现了链表构造还提供了直观展示最终结果的功能[^2]。