Basics

基本操作

• find middle (fast-slow pointers)
• reverse
• merge
• insert
• remove

什么时候用 dummy node

• 链表结构发生变化时
• 也就是当返回的链表的头不确定的时候
• 涉及链表删除操作的时候，稳妥起见都用 dummy node，省去很多麻烦。因为不一定什么时候 head 就被删了
• merge two sorted lists, partition list..

Fast-slow pointers

• middle of linked list
• remove nth node from end of list
• linked list cycle i, ii
• rotate list..

Problems

remove duplicates from sorted list ii: http://www.lintcode.com/en/problem/remove-duplicates-from-sorted-list-ii/

reverse linked list: https://leetcode.com/problems/reverse-linked-list/#/description

reverse linked list ii: http://www.lintcode.com/en/problem/reverse-linked-list-ii/

partition list: http://www.lintcode.com/en/problem/partition-list/

sort list: http://www.lintcode.com/en/problem/sort-list/

• find middle + merge sort

reorder list: http://www.lintcode.com/en/problem/reorder-list/

• find middle + merge + reverse

linked list cycle: http://www.lintcode.com/en/problem/linked-list-cycle/

• fast-slow pointers

rotated list: http://www.lintcode.com/en/problem/rotate-list/

merge k sorted list (k路归并): http://www.lintcode.com/en/problem/merge-k-sorted-lists/

• approach 1: heap
• approach 2: divide & conquer
• approach 3: merge list 2 by 2
• related: merge k sorted arrays, merge 2 sorted list

copy list with random pointer: http://www.lintcode.com/en/problem/copy-list-with-random-pointer/

• approach 1: hash map
• approach 2: no extra space

http://www.lintcode.com/problem/convert-sorted-list-to-balanced-bst/

http://www.lintcode.com/problem/reverse-nodes-in-k-group/

http://www.lintcode.com/problem/delete-node-in-the-middle-of-singly-linked-list/

http://www.lintcode.com/problem/convert-binary-search-tree-to-doubly-linked-list/

https://leetcode.com/problems/remove-nth-node-from-end-of-list/

https://leetcode.com/problems/odd-even-linked-list/

https://leetcode.com/problems/swap-nodes-in-pairs/

LRU Cache

• LinkedHashMap = DoublyLinedList + HashMap
• HashMap<key, DoublyListNode> DoublyListNode { prev, next, key, value; }

Rehashing