LeetCode刷题记录——LinkedList

一共三十来道题，一道能打的都没有！（傲娇脸）

不吹牛了。。。应该是当时做的时候太懒的就没有写笔记。。。

就几道题稍微难一些，其中两道hard的题。还有常考的几道面试热门题，比如翻转链表，判断链表是否有环，找到链表的中间节点，有了这几个操作组合起来可以解决很多问题。

再有就是，headnode真的有用，用过了就会知道，真香！

后续

后来在小黄同学找工作的时候我跟着二刷了一些题，发现自己牛皮吹的是真的大。。。下面记录一些感觉还挺厉害的题目。

138. Copy List with Random Pointer

这道题即使用上了哈希表做起来其实也有一点绕。然后看到了discussion中的最佳解法，才发现牛皮的人是真的牛皮。大神给出了一种不需要格外空间的解法，方法是在原链表的基础上在每个节点后插入一个影子节点，然后操纵影子节点的随即指针，最后把影子链表单独拆出来拆开。思路巧妙不说，还异常简洁易懂。

430. Flatten a Multilevel Doubly Linked List

这道题本来我想的是用递归做，然后看了我自己原来的做法，发现使用非递归做出来的。核心思想就是在每个可能的分叉处把待处理的部分压栈。这个思想基本和非递归遍历二叉树很像了。

206. Reverse Linked List

这道题本身是很简单的，而且有递归非递归两种做法。但是之前我习惯的非递归法是使用三个指针扫过整个链表。看官方给出了另一种解法，从第一个节点开始，不断把当前指针放到头结点前面。和我的三指针法各有利弊。比如在“445. Add Two Numbers II”一题中，一个比较好的解法是先弄出不进位的倒序的相加结果，然后一边进位一边反序。这里的反序就天然适合leetcode官方的反序解法，因为这种反序是类似于从后向前的将原链表倒序，而三指针法是从前向后的将原链表倒序。