動機

Linus Torvalds的雙層ptr的推廣文

原本刪node的方式

ptr指到node,所以要記錄prev,因為不知道下一個是誰,還要處理在head刪的問題

def delNode(head, target):
  prev, cur = None, head

  while cur:
    if cur is target:
      if prev:
        prev.next = cur.next
      else:
        return cur.next
  return head

用雙層ptr

現在我們看next本身!!

next本身有

  1. 自己的node下一步到哪
  2. 下一個node的位置

所以只要看到下一個node是target就可以直接改next!!

Node* delNode(Node* head, Node* target) {
  Node** next = &(head->next);

  for (;*next && *next != target; next = &(*next)->next) ;
  // 當跳出去時一個是到底,一個是下一個是target
  if (*next)
    *next = target->next; // 直接改next的內容
}

Ref

Linked lists, pointer tricks and good taste