2. 两数相加

注意进位
图片.png

19. 删除链表的倒数第 N 个结点

快慢指针，注意判断只有一个元素和删除头结点的情况
图片.png

61. 旋转链表

图片.png

102. 二叉树的层序遍历

广度优先搜索
用队列（切片）缓存下一层的数据并作为下一次遍历的数据
图片.png

138. 复制带随机指针的链表

图片.png

142. 环形链表 II

和简单版本不一样，要获取环的入口结点
关键是要理解该题的 数学思路：

  • 根据数学思维和相应公式，快慢指针都要从头结点出发
  • 使用头结点配合慢指针获取入口结点

图片.png

189. 轮转数组

有三种解法，我想到的其中两种是 拼接数组 和 计算移动后位置放入新数组里
满足空间复杂度为 O(1) 的原地解法思路为：先把数组整体反转，再将数组分割后进行两次局部反转，注意要通过模除计算出分割点

300. 最长递增子序列

动态规划
图片.png

328. 奇偶链表

空间复杂度要求为 O(1)，因此不能额外开辟堆空间，即创建额外的链表
图片.png

430. 扁平化多级双向链表

递归，注意空指针判断
图片.png

707. 设计链表

单链表

图片.png

双链表

图片.png

912. 排序数组

快速排序：原理和思路见：
实现了三数取中优化法，代码稍作改动，去除了部分冗余判断：

  1. func sortArray(nums []int) []int {
  2.     quickSort(nums, 0, len(nums)-1)
  3.     return nums
  4. }
  6. func quickSort(nums []int, left, right int) {
  7.     if left < right {
  8.         index := partition(nums, left, right)
  9.         quickSort(nums, left, index-1)
  10.         quickSort(nums, index+1, right)
  11.     }
  12. }
  14. func partition(nums []int, left, right int) int {
  15.     mid := left + (right - left) / 2
  16.     if nums[left] > nums[right] {
  17.         nums[left], nums[right] = nums[right], nums[left]
  18.     }
  19.     if nums[mid] > nums[right] {
  20.         nums[mid], nums[right] = nums[right], nums[mid]
  21.     }
  22.     if nums[mid] > nums[left] {
  23.         nums[mid], nums[left] = nums[left], nums[mid]
  24.     }
  25.     pivot := nums[left]
  26.     start := left
  27.     for {
  28.         for left < right && nums[right] >= pivot {
  29.             right--
  30.         }
  31.         for left < right && nums[left] <= pivot {
  32.             left++
  33.         }
  34.         if left == right {
  35.             break
  36.         }
  37.         nums[left], nums[right] = nums[right], nums[left]        
  38.     }
  39.     nums[start], nums[left] = nums[left], nums[start]
  40.     return left
  41. }