1. 链表常用操作
相信大家在学习数据结构的过程中已经接触过许多链表相关的题目了,在正式开始刷题之前,我想让大家先回顾一下过去处理链表相关问题时的一些常见操作。
首先肯定就是创建新节点了,如果使用C语言编写代码,我们需要自己用malloc函数分配内存,然后手动初始化节点,而使用C++就简单多了,直接new就行。然后是链表的尾插,这也非常简单,我们定义一个tail指针始终指向链表的尾部,当进行尾插时,令链表尾部的next指向尾插的节点,然后tail指针重新指向新的链表尾部即可。还有就是头插,如果我们直接进行头插操作,需要对链表为空的情况进行处理,但如果引入虚拟头节点newhead的话,就可以省去对边界情况的讨论,只需要令新节点指向newhead的next,然后newhead指向新节点,这样就非常方便的实现了头插。
在这里我还想讲一些做链表题时的常用技巧,首先是画图,这有助于我们直观形象地理解题目,在处理比较复杂地题目时很有帮助;还有就是前面提到过的虚拟头节点,有了虚拟头节点,我们能够省去对许多边界情况的讨论,大大降低了代码编写的复杂程度;最后一点,我们大可不必吝啬定义一些辅助的变量,这能避免我们把自己都搞混乱了,举个例子:
相信大家如果经历过数据结构的卷面考试的话,对这种坑爹的题目肯定是不陌生的,令人看得眼花缭乱,出于考核的目的,这无可厚非,但我们自己写代码就没必要这样折磨自己了吧,直接定义一个next指针,指向prev的next,编写代码将会轻松许多。
2. 两数相加
本题要求我们将以链表形式逆序储存的两个数字进行相加,经常做加法的同学都知道,这实际上是降低了我们编写代码的难度,因为我们的加法运算本来就是从低位到高位进行的呀。所以我们只需要模拟加法这个过程,对两个链表进行遍历,当两个链表非空时进行相加,为了处理进位的情况,我们可以创建变量t来进行辅助运算,根据加法运算逢十进一的性质,把两个链表元素相加的结果加到t,对t取模10后添加到要返回的链表中,t除以10的结果就是进位数更新到t。只要两个链表有一个不为空或者t不为0,我们就继续运算,直到计算完毕为止。
正如我们在常用操作那里提到的,要返回的链表我们也可以设置一个虚拟头节点,这有助于我们更轻松地编写代码,在最后,我们还需要把虚拟头节点new出来的空间销毁掉。
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
{
ListNode *newhead = new ListNode(0);
ListNode *cur = newhead, *cur1 = l1, *cur2 = l2;
int t = 0;
while(cur1 || cur2 || t)
{
if(cur1)
{
t += cur1->val;
cur1 = cur1->next;
}
if(cur2)
{
t += cur2->val;
cur2 = cur2->next;
}
cur->next = new ListNode(t % 10);
t /= 10;
cur = cur->next;
}
cur = newhead->next;
delete newhead;
return cur;
}
};