链表题目的思考

链表是一个比较常见的数据结构,但是leetcode里的题目相对来说不多,题目也不是很难。最重要的思想就是递归的思路。对于每一个节点,都可以看作一个链表的起点。

merge

这类题目就是用一个递归函数,参数是两个头指针,得到新的指针之后,其中一个向后,然后再递归调用就可以。sort list就是一个merge sort的思想

cycle, two pointers

判断有没有环的题目可以使用快慢指针,当两个指针重新相遇的时候可以判断出现环。

删掉倒数节点可以使用两个指针,一个先走k个,之后两个一起走,快的那个到结尾的时候就说明慢指针指向那个节点是需要删除的。

找交点的题目也是两个节点,其实和找环的思路一样,不过是两个指针走到底了从另一边重新开始,基本思路就是两边走的路程一致。

reverse

Reverse 的思想也比较简单,就是记得保存当前的下一个节点。反转链表的思路就是每次把最后一个节点放到表头。分组reverse的话就是链表的思路叠加,先找出前k个,后面的点就是同样的子问题,做完reverse之后就可以接上后面的点。

如果只是print,可以用stack的递归思想,可以做到不使用任何空间。看palindrome可以把一半reverse来比较。

other questions