Linked list

题目列表

别人总结的列表

  • Rotate List
  • Copy list with random pointers
  • Convert sorted list to Binary Search Tree
  • Remove Duplicates
  • Remove Duplicates II

  • Add Two Numbers

  • insertion sort list use a dummy node to add node to new list one at a time

reverse类

  • reverse linked list
  • reverse print list
  • reverse nodes in k group
  • swap nodes in pairs
  • palindrome list
  • reorder list

Merge类

  • merge linked list
  • merge K sorted List

快慢指针类

  • list cycle I, II
  • get kth node ( get middle node)
  • intersection of two lists
  • remove nth node from end of list

题目类型

解题技巧

dummy node

当head不确定是否要保留时，就应该用一个dummy node， 一般用法

dummy = ListNode(0)
dummy.next = head
cur = dummy

merge linked list

这个是很多题目的基础，一定要熟

reverse linked list

最简单的就是建一个Dummy node, 然后不断地将原来List的Node插入到dummy node的后面， 但是这样需要了额外的空间。

更好的方法是用一个variable pre保存前一个node, 一个cur保存现在的Node, 不断地改变这两个node 的指针关系，并且将pre和cur更新向下两个点

tmp

操作linked list的时候，我们经常会改变某些Node的下一个节点， 如果要用到会被改变的node, 要记得用tmp存起来

查找 kth node

对于node之间的距离判断应该弄清楚，比如1st node和nth node之间的距离是n-1, 所以如果从head开始到nth node需要移动n-1步。

while loop从1开始的时候，每移动1步加1，那么终止条件就应该是p < n, 也可以理解为p代表的是 现在指向的是第几个Node。

Reference