反向打印列表
通过next指针进行迭代，直接拼接并打印
使用函数迭代以及列表操作 [ ]+[ ]
- 迭代 return function(head.next)， 并累加当前节点的value [self.val]
- 停止case：当前节点为空，返回空列表
class Solution:
def reversePrint(self, head: ListNode) -> List[int]:
if head:
return self.reversePrint(head.next) + [head.val]
else:
return []
反转链表
方法1：经典双指针指来指去
- 一前一后两个指针，通过更改 cur.next指向pre完成反转
- 记得用 tmp暂存原cur.next， 用于cur指针往后移动
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
cur, pre = head, None
while cur:
tmp = cur.next # 暂存后继节点 cur.next
cur.next = pre # 修改 next 引用指向
pre = cur # pre 进一步
cur = tmp # cur 进一步
return pre
方法2：递归
- 建一个function，用于 pre -> cur 转为 cur -> pre
- 终止条件是找到了最后一个点
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
def recur(cur, pre):
if not cur: return pre # 终止条件
res = recur(cur.next, cur) # 递归后继节点
cur.next = pre # 修改节点引用指向
return res # 返回反转链表的头节点
return recur(head, None) # 调用递归并返回
复制存在random指针的复杂链表
方法1: hash字典
- 先遍历一遍生成一个字典（key = 原节点，value = 新节点）
- 新节点构建方式 Node(value)
- 再遍历一遍，根据原链表的next， random信息，创建新的链表节点信息
注：新节点的next，random都是一个刚建的node，也就是连接到字典的value上
- 首先可能会想到双指针边遍历边复制这种方式, 但是此方式只适合普通链表的复制
由于本题中存在 random 属性，其指向的结点是随机的，因此双指针这种方式不行（因为链表查找元素只能一个一个遍历查找）- 那么问题在于，怎么使其变成可以支持快速访问呢？
--> 使用哈希表， 存储每个结点复制后的新结点；- 在得到新结点与旧结点的映射关系后，怎么进行复制呢？
- 问题转化为 通过某种方式 将新结点按照旧结点的关系进行连线
由于要参照旧结点的关系 ---> 一定需要遍历原始链表- 将newCur 按照 cur 在原始链表中的关系连线；因为是要对 新结点们 进行连线， 因此所有的结点都必须 从 map 中取对应的新结点
newCur.next 对应的 next 在map中的映射为 map.get(cur.next);
newCur.random 对应的 random 在 map中映射为 map.get(cur.random);- 返回头结点, 新链表的头结点也存储在 map中， 因此需要返回 map.get(head)；
"""
# Definition for a Node.
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random
"""
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
if not head:
return None
# 遍历构建hash表，key = cur; value = 新节点
cur = head
dic = {}
while cur:
dic[cur] = Node(cur.val)
cur = cur.next
# 直接返回head
cur = head
# 再遍历，构建random
while cur:
dic[cur].next = dic.get(cur.next)
dic[cur].random = dic.get(cur.random)
cur = cur.next
return dic[head]
紧密复制再拆分
原节点 1 -> 新节点 1 -> 原节点 2 -> 新节点 2 -> ……
- 先对每个节点进行复制，完成 old -> new节点的连接
- 依次按照cur.random，连接好cur.next.random （记得连接到newnode）
- 拆分，同时还原old和new，最终return new head
"""
# Definition for a Node.
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random
"""
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
if not head:
return None
cur = head
# STEP1: 紧贴着每个节点进行复制
while cur:
# 造一个新节点，value和cur一样
new = Node(cur.val)
# 新节点的next与cur一样
new.next = cur.next
# 把它放到cur的下一个
cur.next = new
cur = cur.next.next
# STEP2: 复制random指针
cur = head
while cur:
# 如果有当前的下一个(新构建的复制点) 的random，与当前random同步
if cur.random:
cur.next.random = cur.random.next
# 循环直接指向下一个的下一个
cur = cur.next.next
# STEP3:把复制的新节点们拆出来
# 不仅要拆新的，还要还原旧的
result = newhead = head.next
oldhead = head
while newhead.next:
oldhead.next = oldhead.next.next
newhead.next = newhead.next.next
oldhead = oldhead.next
newhead = newhead.next
# 还原旧链表的最后一个node，指向none
oldhead.next = None
return result
