链表解题常用技巧
- 虚拟头节点
- 快慢指针求中心节点
- 多指针
- 翻转链表
- 链表节点的插入
- 计算链表的长度
第一题:203. 移除链表元素
一、题目描述
二、思路
- 用
newHead
代表新链表的头节点,cur
代表新链表的尾节点,head
代表现链表的头节点。 - 遍历链表节点,若节点不等于被删除的节点值,则用
cur(newTail)
节点的next
指针指向该节点,并且将cur(newTail)
指针指向该节点。 - 新链表的
newHead
一开始为nil
,直到发现第一个不需要被删除的节点,并将newHead
指向该节点(cur(newTail)
也指向该节点)。 - 另一种做法可以新建一个链表,将
newHead
和cur(newTail)
都指向新链表的虚拟头节点
上,当遍历到第一个不需要被删除的节点后,再将newHead
和cur(newTail)
赋值给该节点。
三、代码实现
第二题:2. 两数相加
一、题目描述
二、思路
- 新建一个
链表
,首节点为虚拟头节点
,将head
和last
都指向该虚拟头节点
。 - 遍历待相加的两个链表的
头节点
,新建一个节点,并将value
赋值为两链表相加的和
。 - 将
新建链表
的last
指针指向该新建节点
。 - 若加法有
进位
,则标记有进位
,该节点赋值两链表相加之和的个位数
值即可。 - 若两链表其中一个节点为
null
,则视为0
。 - 若两链表遍历某节点都为
null
,先判断是否有标记进位
,然后退出即可。
三、代码实现
第三题:160. 相交链表
一、题目描述
二、思路
- 两个链表红色部分代表相交,用两个指针分别指向链表头节点。
- 将两个链表分别加上对方的元素,使得两个链表长度一致。
- 从头遍历两个链表,比较指针指向的元素是否相等,最终两个链表将找到
相交节点
。
三、代码实现
class Solution {
func getIntersectionNode(_ headA: ListNode?, _ headB: ListNode?) -> ListNode? {
var A = headA
var B = headB
while true {
if A === B {
return A
}
A = A == nil ? headB : A!.next
B = B == nil ? headA : B!.next
}
}
}
四、类似题目
第四题:86. 分隔链表
一、题目描述
- 时间复杂度要求:
O(n)
,空间复杂度要求:O(1)
二、思路
- 准备两个
空链表
,遍历目标链表,将比特定值小的加入a链表
,将比特定值大的加入b链表
,最终再将a链表
的尾部
与b链表
的头部
拼接在一起。
三、代码实现
四、类似题目
第五题:234. 回文链表
一、题目描述
10600 - 4000 - 2000 - 200 - 300 = 4000 + 800 = 4800 - 2000 = 2800
二、思路
- 找到链表的
中间节点
,然后将中间节点右侧链表翻转
,最后遍历比较左右链表元素是否相同。
三、代码实现
翻转链表
第一季有讲过。- 中间节点利用
快慢指针
得到。