链表是数据结构面试中的高频考点,掌握其操作技巧至关重要。下面整理了五道经典题目,涵盖模拟、指针操作、堆与分治等核心思路。
1. 两数相加
思路分析: 两个链表都是逆序存储数字的,个位对个位,十位对十位。直接遍历相加即可,关键在于处理进位。如果最后还有进位,需要额外创建一个节点存储最高位。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* cur1 = l1, *cur2 = l2;
ListNode* newhead = new ListNode(0); // 虚拟头结点
ListNode* head = newhead; // 尾指针
int t = 0; // 记录进位
while(cur1 || cur2 || t){
if(cur1){
t += cur1->val;
cur1 = cur1->next;
}
if(cur2){
t += cur2->val;
cur2 = cur2->next;
}
ListNode* tmp = new ListNode(t % 10);
head->next = tmp;
head = head->next;
t /= 10;
}
head = newhead->next;
delete newhead;
return head;
}
};
2. 两两交换链表中的节点
思路分析: 通过画图辅助理解指针指向会更直观。这里使用虚拟头结点简化边界处理,注意交换时指针断链和重连的顺序,避免死循环或丢失节点。
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if(!head || !head->next) return head;
ListNode* newhead = new ListNode(0, head);
ListNode* prev = newhead, *cur = newhead->next;
ListNode* next = cur->next, *nnext = cur->next->next;
while(cur && next){
// 交换结点
prev->next = next;
cur->next = nnext;
next->next = cur;
// 为修改下一对结点做准备
prev = cur;
cur = nnext;
if(cur) next = cur->next;
if(next) nnext = next->next;
}
head = newhead->next;
delete newhead;
return head;
}
};
3. 重排链表
思路分析: 这道题的核心策略可以拆解为三步:先找中间节点将链表一分为二,接着将第二条链表逆序,最后合并两条链表。
class Solution {
public:
void reorderList(ListNode* head) {
if(!head || !head->next || !head->next->next) return;
ListNode* slow = head, *fast = head;
// 找到中间结点,将链表断开
while(fast && fast->next){
slow = slow->next;
fast = fast->next->next;
}
ListNode* head2 = new ListNode(0);
ListNode* cur = slow->next;
slow->next = nullptr;
// 反转第二条链表,头插法
while(cur){
ListNode* next = cur->next;
cur->next = head2->next;
head2->next = cur;
cur = next;
}
// 合并两条链表
ListNode* ret = new ListNode(0);
ListNode* prev = ret;
ListNode* cur1 = head, *cur2 = head2->next;
while(cur1){
prev->next = cur1;
prev = prev->next;
cur1 = cur1->next;
if(cur2){
prev->next = cur2;
cur2 = cur2->next;
prev = prev->next;
}
}
delete head2;
delete ret;
}
};
4. 合并 K 个升序链表
思路分析: 合并两个有序列表相对简单,用双指针比较即可。扩展到 K 个时,有两种主流方案:
- 优先队列(堆): 将所有头节点放入小根堆,每次取出最小值加入结果链表,若该节点有后继则推入堆中。时间复杂度 O(N log K)。
- 分治递归: 类似归并排序,将 K 个链表两两分组合并,直到只剩一个。相比逐一合并,这种平衡树式的合并方式能减少比较次数。
方法一:堆优化
class Solution {
public:
struct cmp{
bool operator()(ListNode* l1, ListNode* l2){
return l1->val > l2->val;
}
};
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<ListNode*, vector<ListNode*>, cmp> heap;
for(auto l : lists){
if(l) heap.push(l);
}
ListNode* head = new ListNode(0);
ListNode* prev = head;
while(!heap.empty()){
ListNode* t = heap.top();
heap.pop();
prev->next = t;
prev = prev->next;
if(t->next){
t = t->next;
heap.push(t);
}
}
prev = head->next;
delete head;
return prev;
}
};
方法二:分治递归
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
return merge(lists, 0, lists.size() - 1);
}
ListNode* merge(vector<ListNode*>& lists, int left, int right){
if(left > right) return nullptr;
if(left == right) return lists[left];
int mid = (left + right) >> 1;
ListNode* l1 = merge(lists, left, mid);
ListNode* l2 = merge(lists, mid + 1, right);
return mergeTosort(l1, l2);
}
ListNode* mergeTosort(ListNode* l1, ListNode* l2){
if(!l1) return l2;
if(!l2) return l1;
ListNode cur;
ListNode* prev = &cur;
cur.next = nullptr;
ListNode* c1 = l1, *c2 = l2;
while(c1 && c2){
if(c1->val <= c2->val){
prev->next = c1;
c1 = c1->next;
} else{
prev->next = c2;
c2 = c2->next;
}
prev = prev->next;
}
if(c1) prev->next = c1;
if(c2) prev->next = c2;
return cur.next;
}
};
5. K 个一组翻转链表
思路分析: 按 k 个为一组进行分组,组内反转,并记录反转后的头尾节点以便连接前后段。可以先统计总长度确定需要翻转多少组,然后重复执行长度为 k 的局部反转逻辑。
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
int n = 0;
ListNode* cur = head;
while(cur){
n++;
cur = cur->next;
}
n /= k;
ListNode* newhead = new ListNode(0);
ListNode* prev = newhead;
cur = head;
while(n--){
ListNode* tmp = cur;
for(int i = 0; i < k; i++){
ListNode* next = cur->next;
cur->next = prev->next;
prev->next = cur;
cur = next;
}
prev = tmp;
}
prev->next = cur;
prev = newhead->next;
delete newhead;
return prev;
}
};
