Linked List

Linked List

Overview

Fast & Slow Pointers

• Linked List Cycle
• Linked List Cycle II
  • 其实不用快慢指针，而用一个hashset的话写法更简单。如果要求O(1)的space complexity 那么只能用快慢指针。
  • 找到相遇点之后，再从头以相同速度走一次，相遇的那个点就是第一次相遇点。
• Remove Duplicates from Sorted List II
  • Maintain two pointers, pre always points to the previous distinct point, and head always points to the last point of duplicate number
  • 使用while定位非重复元素，如果只是找特定值，也可以把条件写进大的while中 参考:Remove Linked List Elements
• Remove Nth Node From End of List
• Middle of the Linked List
• Sort List
• Palindrome Linked List
  • 最方便的当然是转成array然后比较
  • 如果要求space complexity O(1)可以找中点，反转后半段，再比较
  • 大杂烩
• Reorder List
  • 大杂烩2

Others Problems

• Reverse Linked List
• Reverse Linked List II
  • Dummy Node 可以很方便的cover corner case
• Merge k Sorted Lists
  • Use a PriorityQueue to maintain the all lists head while searching the min val
• Copy List with Random Pointer
  • Space complexity O(1) 的方法：复制当前的插入中间，然后再解链
• Remove Duplicates from Sorted List
• Partition List
  • Using two pointers
• Remove Linked List Elements
• Insert into a Sorted Circular Linked List
  • 太多corner case
  • 注意一下用一个boolean变量来复用代码的操作
• Flatten a Multilevel Doubly Linked List
• Intersection of Two Linked Lists
• LRU Cache