反向打印列表

通过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上

1. 首先可能会想到双指针边遍历边复制这种方式, 但是此方式只适合普通链表的复制
   由于本题中存在 random 属性，其指向的结点是随机的，因此双指针这种方式不行（因为链表查找元素只能一个一个遍历查找）
2. 那么问题在于，怎么使其变成可以支持快速访问呢？
   --> 使用哈希表， 存储每个结点复制后的新结点；
3. 在得到新结点与旧结点的映射关系后，怎么进行复制呢？
4. 问题转化为 通过某种方式 将新结点按照旧结点的关系进行连线
   由于要参照旧结点的关系 ---> 一定需要遍历原始链表
5. 将newCur 按照 cur 在原始链表中的关系连线；因为是要对 新结点们 进行连线， 因此所有的结点都必须 从 map 中取对应的新结点
   newCur.next 对应的 next 在map中的映射为 map.get(cur.next);
   newCur.random 对应的 random 在 map中映射为 map.get(cur.random);
6. 返回头结点, 新链表的头结点也存储在 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