LeetCode 补充题 172. 用单链表实现队列
题目描述
牛客原题： ✅ 补充题 172. 用单链表实现队列
用单链表实现整数队列，提供以下操作：
offer：从尾部入队。poll：从头部出队并返回该元素。peek：读取队首元素，不删除。isEmpty：判断队列是否为空。各操作最坏时间复杂度为
O(1)。空队列查询或出队时，Java 返回null，Go 返回(value,false)。
示例 1：
输入：
操作 = [offer(3), offer(5), poll(), peek(), poll(), isEmpty()]
输出：查询结果 = [3,5,5,true]
解释：offer不返回查询值。首次出队得到 3，peek读取 5 且不删除，第二次出队后队列为空。
提示：
-
牛客通过
push、pop、front操作驱动队列，对应本文的offer、poll、peek；打印练习结果时将空队列的失败状态输出为error。 - 队列存储整数，先进先出，各操作最坏
O(1)。 - 空队列读取或出队时，Java 返回
null，Go 返回失败标志。
题意分析
先进先出要求从链头删除、从链尾追加。若只保存头指针，入队寻找尾节点需要线性时间，因此同时保存
head、tail，使每次操作只改固定数量的指针。
解法：头尾指针维护链式队列
核心思路
[!blue]
非空时
head指向最早入队节点，tail指向最后入队节点且tail.next为空；空队列则两个指针同时为空。入队创建新节点，非空时接到尾部，空时同时建立头节点，最后更新tail。出队先保存头值，再令
head = head.next。若新头为空，说明最后一个节点已被删除，必须同步清空tail，否则下一次入队会接到已脱离队列的旧节点上。
peek只读头值，isEmpty检查头指针；空队列用null或独立失败标志表示，不用某个整数值冒充空状态。所有入队、出队和查询都无需遍历。
解题步骤
- 初始化 head、tail 为空。
- 入队时把新节点接到 tail 后；空队列同时设置 head。
- 出队取 head 并前移；删掉最后一个节点时同步清空 tail。
代码实现
class LinkedQueue {
private static class Node {
int value;
Node next;
Node(int value) {
this.value = value;
}
}
private Node head;
private Node tail;
public void offer(int value) {
Node node = new Node(value);
if (tail == null) {
head = node;
} else {
tail.next = node;
}
tail = node;
}
public Integer poll() {
if (head == null) {
return null;
}
int value = head.value;
head = head.next;
if (head == null) {
tail = null;
}
return value;
}
public Integer peek() {
return head == null ? null : head.value;
}
public boolean isEmpty() {
return head == null;
}
}
type queueNode struct {
value int
next *queueNode
}
type LinkedQueue struct{ head, tail *queueNode }
func (q *LinkedQueue) Offer(value int) {
node := &queueNode{value: value}
if q.tail == nil {
q.head = node
} else {
q.tail.next = node
}
q.tail = node
}
func (q *LinkedQueue) Poll() (int, bool) {
if q.head == nil {
return 0, false
}
value := q.head.value
q.head = q.head.next
if q.head == nil {
q.tail = nil
}
return value, true
}
func (q *LinkedQueue) Peek() (int, bool) {
if q.head == nil {
return 0, false
}
return q.head.value, true
}
func (q *LinkedQueue) IsEmpty() bool {
return q.head == nil
}
复杂度分析
- 时间复杂度：每个操作时间 $O(1)$。
- 空间复杂度：存储n个元素占 $O(n)$ 空间。
关键点总结
[!green]
head 指向最早入队元素，tail 指向最后入队元素；空队列两个指针都为空，才能保证后续重新入队正确。
易错点总结
[!yellow]
最后一个节点出队后必须清空tail，否则下一次入队可能接到失效链表上。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 707. 设计链表 | 中等 | 链式队列的入队、出队分别是尾插和删除头节点，可直接复用链表连接操作；额外保存尾指针即可省去入队时的定位遍历。 |