剑指 Offer 06. 从尾到头打印链表
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def reversePrint(self, head: ListNode) -> List[int]:
res = []
while head:
res.append(head.val)
head = head.next
return res[::-1] #倒序读取方法二:使用递归 递归停止条件：链表中无节点；否则就将当前节点加至列表末尾
class Solution:
def reversePrint(self, head: ListNode) -> List[int]:
return self.reversePrint(head.next) + [head.val] if head else []剑指 Offer 24. 反转链表
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
pre = None
cur = head
while cur:
tmp = cur.next # 保留旧的前驱节点
cur.next = pre # 更新前驱节点
# 为下次更新做准备
pre = cur # 暂存当前节点
cur = tmp # 访问下一个节点准备更新
return pre递归方法 写递归是可以从以下两点考虑：1.最小实现；2.递归结束条件
def recur(cur,pre):
if cur == null: # 返回条件
return pre
else: # 最小形式
tmp=cur.next
cur.next = pre
return recur(tmp,cur)剑指 Offer 35. 复杂链表的复制
题目在链表中添加了一个指向其他任意节点的指针。
对于复制，直接想到的是直接返回输入不久好了吗？这个提的意思是要根据输入重新建立一个相同链表。我认为这是复制代码至少是要体现在内存上使用新空间存储同时保证节点间的联系。这一个题还挺难
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
# 考虑构建 原链表节点 和 新链表对应节点 的键值对映射关系
if not head : return None
dic = {}
cur = head
res = Node
# 复制链表建立新节点；因为键是节点对象所以不会重复 dic 旧节点： 新节点 由此建立映射
while cur:
dic[cur] = Node(cur.val)
cur = cur.next
# 存储节点之间的索引
while cur:
dic[cur].next = dic.get(cur.next) # get方法返回指定键的值
dic[cur].random = dic.get(cur.random)
cur = cur.next
return dic[head]方法二：建立原节点新节点的拼接链表
def copyRandomList1(self, head: 'Node') -> 'Node':
if not head: return None
cur = head
while cur:
tmp = Node(cur.val) #设立新节点，且值与前面的相同
# 插入旧节点间
tmp.next = cur.next
cur.next = tmp
cur = tmp.next
cur = head
while cur: #建立随机指向
if cur.random:
cur.next.random = cur.random.next # 这个等式很重要,是新节点的random关系与旧节点相同
cur =cur.next.next
# 拆分
cur = res = head.next
pre = head
while cur.next:
pre.next = pre.next.next
cur.next = cur.next.next
# pre 的节点已经更新完成，随意下面两行只用一个next
pre = pre.next
cur = cur.next
# 新插入的节点已经指向null了所以不用修改
pre.next = None
return res
