编写单链表比:并实现链表合并
时间: 2024-09-20 13:02:09 浏览: 7
单链表是一种线性的数据结构,其中每个节点包含数据和指向下一个节点的指针。相比于数组,链表的优势在于插入和删除元素的时间复杂度通常较低,因为只需要修改相邻节点的指针即可,而不需要移动大量的元素。
编写单链表的基本操作包括创建节点、添加节点到列表尾部(如`append`)、查找特定值(如`search`),以及删除指定节点等。如果需要合并两个已排序的单链表,可以采用迭代或递归的方式:
**迭代法:**
1. 定义一个新的头节点`newHead`和两个指针`p1`和`p2`分别指向两个输入链表的头部。
2. 比较两个指针所指的节点值,将较小的节点放入新链表,并移动对应指针。
3. 当其中一个链表为空时,将另一个链表剩余部分接到新链表的尾部。
**递归法:**
1. 如果一个链表为空,则直接返回另一个链表。
2. 否则,比较两个链表头节点的值,选择较小的一个作为新的头节点,并递归地合并剩余部分。
以下是Python伪代码示例:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def merge_sorted_lists(l1, l2):
if not l1 or not l2:
return l1 or l2
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
```