一、链表知识总结 二、链表做题心得
链表定义
class LinkNode(self, val=None):
# self表示创建的对象自身，定义了对象自带的属性和方法
self.val = val
self.next = None
# 实例化链表并用头插法添加元素
# 已存在头节点
head = LinkNode(val1)
def createLink_head(val):
node = LinkNode(val)
head.next = node
# 把头节点往下移动继续添加
head = node
链表的增删改操作
# 为了方便对头节点进行删除或增加操作，增加一个虚拟头节点
dummy_head = LinkNode(next=head)
# 虚拟头节点也是链表节点类的一个，下一个引用指向头节点
new_node = LinkNode(val=3)
# 索引值是从0开始的，添加到索引值为3的位置上
posi = 3
for i in range(posi):
dummy = dummy.next
new_node.next = dummy.next
dummy.next = new_node
链表的反转
- 不必再新开空间存放新链表
- 只需要每个链表里的两两节点进行反转，遍历到最后，所有节点都反转完毕
- 递归解决链表反转
def reverseLinkList(head):
if not head or not head.next:
return head
tail = reverseLinkList(head.next)
head.next.next = head
head.next = None
return tail
- 链表的赋值问题：
链表题知识总结
- 循环关系
逻辑关系： while + if： 循环直到if条件不成立 while ： if： else： 进入循环若if不成立则进行else操作，循环直到while条件不成立
- 数学方法解决链表寻找链表环入口问题
- 递归算法的应用
- 大问题可以被拆分为有限个小问题
- 每一层的解决方法相同
- 存在最小的子问题
- 1⃣️在递进的过程中解决小问题（代码写在调用自我函数之前，动作在“递”之前发生）
- 2⃣️在返归的过程中解决问题（代码写在调用函数之后，边归边解决问题）
- 解决链表反转时tail值不变问题
- 输出发现tail值一直不变
# 递归解法, 头节点为head,传入一个head参数为ListNode类 def reverseLinkList(head): if not head or not head.next: return head # print('before') tail = reverseLinkList(head.next) # print("tail:", tail.val,end=',') # head.next.next = head head.next = None print("head:", head.val,end=',') return tail # 输出结果 tail: 7,head: 6,tail: 7,head: 5,tail: 7,head: 4,tail: 7,head: 3,tail: 7,head: 2,tail: 7,head: 1, - 为什么每一轮tail的值都相同 ①当递归到最后一层时返回值为尾tail=尾节点值， ②最后一层递归的最后一行又有一个返回值tail，相当于把tail赋给之后的每一层递归值，所以tail的值不变
- Ⅱ为什么head的值会改变 因为head在每一层递归调用中都被赋了一个不同的值， 所以返回之时head的每一层的值也都不同， 所以每次进行两两之间的反转操作都在不同的节点之间
- 输出发现tail值一直不变
