Day2.1 剑指 Offer 06. 从尾到头打印链表

输入一个链表的头节点，从尾到头 反过来返回每个节点的值（用数组返回）
eg:
输入：head = [1,3,2]
输出：[2,3,1]

方案1： 直接向List中倒着插入

建立一个list
从前到后遍历链表 ，将值从list的头一一插入 【用了List内置函数】

时间复杂度：n
空间复杂度: n

  1. class Solution:
  2.     def reversePrint(self, head: ListNode) -> List[int]:
  3.         re_list = []
  4.         # 遍历链表 将值从头一个个插入list
  5.         while(head):
  6.             # head 后面也是带着val
  7.             if head != None:
  8.                 re_list.insert(0,head.val) # TODO: 耗时
  9.             head = head.next
  11.         return re_list

执行用时：44 ms, 在所有 Python3 提交中击败了51.37%的用户
内存消耗：16.3 MB, 在所有 Python3 提交中击败了70.68%的用户

方案2：反转链表后打印
时间：n
空间：由反转的算法决定

  1. class Solution:
  2.     def reversePrint(self, head: ListNode) -> List[int]:
  3.         re_list = []
  4.         # 反转链表
  5.         head = self.reverse(head)
  7.         # 将链表打印到list
  8.         while(head):
  9.             re_list.append(head.val)
  10.             head = head.next
  12.         return re_list
  14.     def reverse(self,head):
  15.         pre = None # 不能是 ListNode() 不然就会带着这个节点
  16.         nxt = ListNode()
  18.         while(head):
  19.             nxt = head.next    # 保护断点
  20.             head.next = pre    # 切开断点
  22.             # pre head 向前移动一个单位
  23.             pre = head         
  24.             head = nxt 
  26.         return pre

执行用时：36 ms, 在所有 Python3 提交中击败了82.00%的用户
内存消耗：16.3 MB, 在所有 Python3 提交中击败了51.57%的用户

时间快了很多，空间感觉基本没变，是中间变量占位置了吗 ？

Day2.2 剑指 Offer 24. 反转链表

有意思了 这个题就是2.1的第二种解法用到的一个部分
其实这个题已经是第三次做了
但是感觉还是不熟练

方案1： 迭代

其实就是：前继，后缀 指针的移动,主要的核心点有三个部分

  1. while循环的判别条件： 用head，还是head.next —- None节点索引next会出错 所以用前者
  2. pre , head, nxt 的轮回，旧值移出，新值就要移动入

  3. return的是什么 head还是pre? 因为pre是跟着链到最后的男人。而且不是空，所以是pre 

    1. class Solution:
    2.  def reverseList(self, head: ListNode) -> ListNode:
    3.      pre = None
    5.      while(head):
    6.          nxt = head.next
    7.          head.next = pre
    8.          pre = head
    9.          head = nxt
    11.      return pre

    执行用时：44 ms, 在所有 Python3 提交中击败了26.46%的用户
    内存消耗：15.5 MB, 在所有 Python3 提交中击败了69.03%的用户

但是结果不太好
后面补充一个好一些的结果

减少一个中间变量，可以一句遍历：

  1. class Solution:
  2.     def reverseList(self, head: ListNode) -> ListNode:
  3.         pre = None
  5.         while(head):
  6.             head.next,pre, head = pre,head,head.next
  8.         return pre

执行用时：40 ms, 在所有 Python3 提交中击败了45.96%的用户
内存消耗：15.5 MB, 在所有 Python3 提交中击败了73.95%的用户

稍稍好一点点

当然还可以用递归的方法实现: 后序遍历

方案2：递归

参考的labuladong的算法小抄中284页 — 秀操作之反转整个链表

  1. class Solution:
  2.     def reverseList(self, head: ListNode) -> ListNode:
  3.         # Step1: base case
  4.         if (head == None or head.next == None ):
  5.             return head
  7.         # Step2: recursion -- 深度优先
  8.         last = self.reverseList(head.next)
  10.         # Step3: deal end 
  11.         head.next.next = head
  12.         head.next = None
  14.         return last

我的理解：
Step2处的 last 处递归下去只为了拿到 Step1 处的底，也就是最后一个节点

在递归压栈回传的时候，head.next 后的链表一个个反转了过来
【假设只有两个节点 你寻思一下是不是可以反转】

在最后，last成为了新链表的头，head.next 成为了新链表的尾。

还需要将head排到head.next的后面
而且最后head后面要以None收尾
即

  1. head.next.next = head
  2. head.next = None

执行用时：32 ms, 在所有 Python3 提交中击败了86.59%的用户
内存消耗：19.6 MB, 在所有 Python3 提交中击败了12.89%的用户
其实递归也没有那么香。
当压栈数量很大的时候，非常不利

Day2.3 剑指 Offer 35. 复杂链表的复制

复制一个复杂链表。
在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null

md ，中等题就这么复杂吗？mmp
题解都不想看 mmp 走了走了 下次再看 — 直接往后走