链表的访问
1、LeetCode #2 两数相加(解题:通过依次遍历两个链表,不断构造出新节点,添加到我们的结果链表中—需要注意进位问题)
2、LeetCode #21 合并两个有序链表(解题:可以使用递归,也可以使用迭代,通过遍历两个链表(需要两链表的节点同时存在才可以比较)进行比较,加入较小的加入到结果链表,遍历结束,说明最多只有一条链表可能还没遍历完,直接加入到结果链表的末尾即可)
3、LeetCode #141 环形链表(解题:设置快慢指针,快指针一次走两步,慢指针一次走一步,如果成环,那么快指针总有那么一个时机能追上慢指针)
4、LeetCode #142 环形链表II 找到环的入口(解题:假设从头指针走到环入口为a, 当慢指针走到入口时,快指针已经走了2a,再假设快指针与慢指针之间相差x步,那么可以得到环的长度为a(快指针比慢指针多走了a步) + x,快指针需要在走x次就能追上慢指针,也就是说慢指针此时从入口点再走x步就会和快指针相遇,而环的长度为a + x,也就是说 ===》 从快慢指针相遇的点开始,在走a步就会到入口点 ==》 此时我们只需要重新设置一个指针,从头开始,该指针与慢指针相遇的点就是入口点)
5、LeetCode #109 有序链表转换为二叉搜索树(解题:因为需要高度平衡,所以我们需要先找到有序链表的中位数 ==》 使用快慢指针法,初始时,快指针fast和慢指针slow均指向链表的左端点left。我们将快指针fast向右移动两次的同时,将慢指针slow向右移动一次,直到快指针到达边界(即快指针到达右端点或快指针的下一个节点是右端点)。此时,慢指针对应的元素就是中位数。在找出了中位数节点之后,我们将其作为当前根节点的元素,并递归地构造其左侧部分的链表对应的左子树,以及右侧部分的链表对应的右子树)
6、LeetCode #114 二叉树展开为链表 (解题:因为需要返回的链表顺序要和先序遍历,一样,所以我们可以对二叉树进行先序遍历,由于二叉树展开为链表后会破坏二叉树的结构(left为null, right为val),因此前序遍历后,我们需要更新每个节点的左右子节点信息)
链表的反转
1、LeetCode #61 旋转链表(解题:定义一个指针,从头开始,遍历到尾节点,这样可以获取到链表的长度,链接链表的首尾节点,通过观察可得出规律,尾指针需要向前移动length - k次到达旋转后的尾节点,断开即可)
2、LeetCode #24 两两交换链表中的节点(解题:迭代反转,设置一个虚拟头节点指向头节点,在定义一个指针从虚拟头节点开始(该指针永远指向需要反转的两个节点的前一个节点,这样迭代反转,最后返回虚拟头节点的下一个节点即可))
3、LeetCode #25 K个一组反转链表(解题:拆分成反转链表的前N个节点和判断链表是否满足K个)
4、LeetCode #206 反转链表(解题:递归)
5、LeetCode #92 反转链表II(解题:拆分成反转链表的前N个节点)
6、LeetCode #86 分隔链表(解题:构造两个链表,一个用于存储小于k的,一个用于存储大于都等于k的,最后将两条链表连接起来即可)
链表的删除
1、LeetCode #19 删除链表的倒数第N个节点(解题:找到链表的倒数第n+1个节点,然后指向倒数第n个节点的下一个节点即可,要找到倒数第N+1个节点,需要先得出链表的长度,然后通过使用虚拟头节点,来移动到倒数第N+1个节点的位置)
2、LeetCode #83 删除排序链表中的重复节点(解题:定义一个指针从头节点开始移动,判断当前节点和下一个节点值是否相等,如果相等,直接将当前节点的next指针域指向当前节点的下一个节点的下一个节点(指向后不要移动指针,因为当前节点和下一个节点(新)可能也存在相等),如果不相等,指针后移即可)
3、LeetCode #82 删除排序链表中的重复节点II(设置两个指针用于判断,需要使用虚拟头节点)