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;
}
ListNode* result = newhead->next;
delete newhead;
return result;
}
};
2. 两两交换链表中的节点
思路: 这道题主要考察指针的灵活操作。画图理解后不难发现,每次只需调整四个指针的关系即可完成一对节点的交换。
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if(!head || !head->next) head;
ListNode* newhead = (, head);
ListNode* prev = newhead;
ListNode* cur = newhead->next;
ListNode* next = cur->next;
(cur && next){
prev->next = next;
cur->next = next->next;
next->next = cur;
prev = cur;
cur = next->next;
next = cur ? cur->next : ;
}
ListNode* result = newhead->next;
newhead;
result;
}
};

