Leetcode-Linked list 心得

Leetcode-Linked list 解題心得¶

一個最基本的linked list架構會像以下

class ListNode:    def __init__(self, x):        self.val = x        self.next = None

一個叫做ListNode 的class，可以指定一或多個值(上面範例是一個值val, x)

每一個位置稱之為一個node，慣用上.next會指向下一個node保存的位址

有點像小學生大家手搭肩，你可以看到下一個人在哪邊

其中一個基本題型是考如何去重新指向，比方說原本是1->2->3，現在想要剔除偶數的node，就需要把1 的.next保存，在取得3，重新指向

還有一種特殊題型是檢查是否存在迴圈，即node一值往下會永無止盡，經典解法是套slow/fast兩個檢查點，slow一次進入下一個node，fast一次兩個node，如此一來，如果node中存在迴圈，fast總有一天會追上slow，範例如下

slow, fast = head, head  while fast and fast.next:      slow=slow.next      fast=fast.next.next      if slow==fast:          return True  return False

許多剩餘題型都是類似的變種，比較會忘記的是

• edge case 如果一開頭就給空node也要記得考慮
• 如果是node重新排序的題型，要記得有些情況下，答案最尾端node的next一開始有給值，因此要再重新assign .next=None