精选习题解析
链表是数据结构中的基础组件,但在实际编码中,指针的指向关系往往容易出错。下面通过五道经典题目,梳理链表操作的常见套路。
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) head;
ListNode* newhead = (, head);
ListNode* prev = newhead, *cur = newhead->next, *next = cur->next, *nnext = cur->next->next;
(cur && next) {
prev->next = next;
cur->next = nnext;
next->next = cur;
prev = cur;
cur = nnext;
(cur) next = cur->next;
(next) nnext = next->next;
}
head = newhead->next;
newhead;
head;
}
};

