動機

就faq，所以把記得的列一下

insert

def insert_node(head,n,newnode):
  prev = None
  while head and n != 0:
    prev = head
    head = head.next
    n -= 1
  if n == 0:
    if prev:
      prev.next = newnode
      newnode.next = head
    else:
      newnode.next = head
  else:
    raise RuntimeError()

delete

def del_node(head,n):
  cur = head
  ret = None
  prev = None
  while cur:
    if cur.val == n:
      if prev:
        prev.next = cur.next
      elif not ret:
        ret = cur.next
  if not ret:
    ret = head
  return ret

reverse

這邊給的revserse是[a,b)

recursive

先到最後一個，之後回去時再一層一層接回去

def rev(a,b): # [a,b)
  if a.next is b:
      return [a, a]
  else:
      h,d = rev(a.next,b)
      d.next = a
      return [h,a] # head, tail

iterative

1 -> 2 -> 3，2 -> 1 , 3，3- > 2 -> 1 每次交換完，都是被換(1換2)的變成下一次loop要被換下去的(2換3) 所以可以給出兩個ptr，一個是要被換的，另一個是與之交換的

def rev(a,b): # [a,b)
  ptr = a
  ptr_next = a.next
  a.next = None #第一次換要把連結打斷，不然會loop
  while ptr_next is not b:
      tmp = ptr_next.next
      ptr_next.next = ptr # 2 指向 1
      ptr = ptr_next # 下一次處理2
      ptr_next = tmp
  return [ptr,a] # head, tail

找中點

j走的距離是i的兩倍!! 所以當j到底時i剛好在一半

def mid(root):
  i = root
  j = root
  while j and j.next:
    i = i.next
    j = j.next.next
  return i

關於sort

要用merge sort，不能用quick sort，qsort的worst case可以到n^2，但merge都是nlogn