LeetCode刷了一百多道题,决定来发小小的总结。这篇博客主要对LeetCode中链表标签下的题目进行总结,linked-list标签下总共有27道题,这些题目较为全面的考察链表操作:插入、删除、反转、交换、合并、环路检查等。

使用哑节点

哑节点就是第一个没有用的辅助节点,可以使遍历链表的代码更加优雅(具体来说就是不需要对第一个节点做特殊处理)。

例如我们创建一个链表:

dummy就是哑节点, return dummy.next; 在很多情况下可以解决极端情况处理的问题 。

头插法与尾插法

头插法与尾插法不仅是重要的创建链表的方法,尤其是在要求不改变结点值的情况下,可以使用头插法来反转链表。

头插法:就是按照节点逆序方法逐渐将节点插入到链表的头部,最后产生的链表是逆序的。

尾插法:就是按照节点顺序方法将节点插入到链表的尾部,比头插法复杂两点:一是开始时需要创建第一节点,二是结束时需要将尾部指针指向NULL。

快慢指针法

快慢指针法有两个作用,第一个作用是找到链表的中间位置,第二个作用是找到链表中存在的闭合环路。

快慢指针法就是,通过两个指针,块指针一次移动两格,慢指针一次移动一格,如果链表中无环,那么两个指针永远不会相遇,并且块指针走过的步长是慢指针走过步长的两倍。

如果链表中有环路,还可以通过快慢指针法找到环开始的位置,具体参见LeetCode#141和#142。

改变父指针指向的值

在使用单链表情况下,我们很难追溯到父节点,于是父节点指针的改变将非常困难。那么我们可以选择改变当前节点的值,可以等效作改变了父节点的指向。

发表评论

电子邮件地址不会被公开。 必填项已用*标注