链表建立、合并、删除、查找等操作的与运行语句及知识点
时间: 2024-10-07 17:08:11 浏览: 6
链表是一种线性数据结构,它的节点包含数据和指向下一个节点的指针。对于链表的基本操作,我们可以详细说明一下:
1. **建立链表**:
- 创建一个新的节点,设置其数据(通常是初始化为None或0)以及一个空的指针(next=None),然后将新节点添加到链表的开始(头结点)或末尾(尾插法)。
```python
class Node:
def __init__(self, data):
self.data = data
self.next = None
# 创建一个新节点并连接到链表头部
head = Node(1)
if current_head is not None:
current_head.next = head
else:
current_head = head
```
2. **合并链表** (两链表相加):
- 定义两个指针分别遍历两个链表,逐位相加并将结果存储在新的节点中,同时更新指针。
```python
def merge_lists(l1, l2):
dummy = Node(0) # 新链表的头节点
current = dummy
carry = 0
while l1 or l2:
a = l1.val if l1 else 0
b = l2.val if l2 else 0
sum_ = a + b + carry
carry = sum_ // 10
current.next = Node(sum_ % 10)
current = current.next
if l1: l1 = l1.next
if l2: l2 = l2.next
if carry > 0: current.next = Node(carry) # 如果有进位,追加最后一个节点
return dummy.next
```
3. **删除节点**:
- 删除指定值的节点通常需要分为查找节点和修改链接两步。查找目标节点,如果找到则更新前一个节点的`next`指针跳过它。
```python
def delete_node(head, key):
if head is None or head.data == key:
return head.next
current = head
while current.next and current.next.data != key:
current = current.next
if current.next is not None:
current.next = current.next.next
return head
```
4. **查找节点**:
- 从头节点开始逐个比较,直到找到匹配的值或者遍历完整个链表。
```python
def search_node(head, target):
current = head
while current:
if current.data == target:
return True
current = current.next
return False
```