剑指Offer（数据结构与算法面试题精讲）C++版——day9

题目一：链表中的数字相加

    题目：给定两个表示非负整数的单向链表，请问如何实现这两个整数的相加并且把它们的和仍然用单向链表表示？链表中的每个节点表示整数十进制的一位，并且头节点对应整数的最高位数而尾节点对应整数的个位数。例如，在图4.10（a）和图4.10（b）中，两个链表分别表示整数123和531，它们的和为654，对应的链表如图4.10（c）所示。

    这里可以使用模拟两个正整数相加的方式来解决问题。鉴于链表是从高位到低位排序的，这与我们日常从个位开始相加的运算习惯不符，所以需要先对链表进行一次反转操作。将两个链表反转后，设置两个指针，分别指向这两个链表的第一个节点，让它们同时从个位开始相加。在相加过程中，要仔细记录每次相加产生的进位数，因为像 8 + 7 等于 15 这样的情况，就会产生进位 1 并要参与下一位的运算。当两个链表的节点都处理完后，可能仍有进位，此时要特殊处理。由于前面我们进行了链表反转，为了得到最终正确的结果，还需要对得到的数字所构成的链表再进行一次反转操作，通过以上这些步骤即可得到最终答案，具体实现代码如下：

linkList sumLinkList(linkList head1,linkList head2) {linkNode *p=head1, *q=head2,*head=nullptr,*next=nullptr;int plus=0,data=0;bool isFirst=true;while(p&&q) {data=(p->data+q->data+plus)%10;plus=(p->data+q->data+plus)/10;linkNode * node=new linkNode(data);if(isFirst) {head=node;next=head;isFirst=false;} else {next->next=node;next=node;}p=p->next;q=q->next;}while(p) {data=(p->data+plus)%10;plus=(p->data+plus)/10;linkNode * node=new linkNode(data);if(isFirst) {head=node;next=head;isFirst=false;} else {next->next=node;next=node;}p=p->next;}while(q) {data=(q->data+plus)%10;plus=(q->data+plus)/10;linkNode * node=new linkNode(data);if(isFirst) {head=node;next=head;isFirst=false;} else {next->next=node;next=node;}q=q->next;}if(plus) {linkNode * node=new linkNode(plus);next->next=node;next=node;}next->next=nullptr;head=reverseList(head);return head;
}

    补充说明，为了让代码不至于太长，这里只放核心代码，这里sumLinkList函数的两个参数分别为已经反转的两个链表，至于模拟数据以及输出结果，新开一个公开的资源链接，这样便能够方便大家详细复盘了。

题目二：重排链表

    题目：给定一个链表，链表中节点的顺序是$L_0\to L_1\to L_2\to \cdots \to L_{n-1}\to L_n$，请问如何重排链表使节点的顺序变成$L_0\to L_n\to L_1\to L_{n-1}\to L_2\to L_{n-2}\to \cdots$？例如，输入图4.12（a）中的链表，重排之后的链表如图4.12（b）所示。

    这道重排链表的题目与考研408中出现的链表重排问题比较相似。考研408中的链表重排重点在于奇偶重排列，而本题则要求将链表前半段保持正序，后半段进行逆序处理。
    从实现角度来看，虽然整体思路不算特别复杂，但在操作过程中需要着重注意原链表长度的奇偶性，当原链表长度为偶数时，处理流程相对清晰简单，只需让前半段链表维持原本的顺序不变，后半段链表执行逆序操作，最后将两段链表进行交叉组合，就能达成重排的目的。
    当原链表长度为奇数时，最中间的那个节点要划分到前半段链表中，后续步骤和偶数长度时类似，先对后半段链表进行逆序，再将前后两段链表交叉合并。为了顺利实现这一系列操作，我们可以先对链表进行一次完整遍历，在这个过程中不仅能判断出链表长度的奇偶性，还能精确获取链表的具体长度数值。之后利用快慢指针的方法，先让快指针前进链表长度一半的距离，接着快慢指针同步移动，从而实现链表前后段的划分。划分完成后，对后半段链表进行逆序处理，最后通过交叉合并的操作，就能得到符合题目要求的重排链表结果了，具体的代码实现如下所示：

linkList convertList(linkList head) {linkList p=head;linkNode *start=head,*end=head,*mark=nullptr,*q=nullptr,*pre=nullptr;int count=0,gap=0;while(p) {//计算链表长度 p=p->next;count++;}gap=count/2;while(gap--) {//后半段指针先走gap if(gap==0) {mark=end;}end=end->next;}if(count%2==0) {//根据就行拆分成两段 mark->next=nullptr;} else {mark=end->next;end->next=nullptr;end=mark;}end=reverseList(end);p=head,q=end;while(q) {//交叉合并 mark=p->next;//存储两个链表下次遍历的节点 pre=q->next;p->next=q;q->next=mark;p=mark;q=pre;}return head;
}

题目三：回文链表

    题目：如何判断一个链表是不是回文？要求解法的时间复杂度是O(n)，并且不得使用超过O(1)的辅助空间。如果一个链表是回文，那么链表的节点序列从前往后看和从后往前看是相同的。例如，图4.13中的链表的节点序列从前往后看和从后往前看都是1、2、3、3、2、1，因此这是一个回文链表。

    这里有一个额外要求，时间复杂度为O(n)，并且不能超过O(1)的辅助空间，可以直接使用前面一题的思路，先扫描一次链表，记录链表中含有奇数个节点还是偶数个节点，然后和前面一样使用快慢指针，如果是偶数个那么快指针先走一半，如果是奇数个节点，那么快指针都一半+1个节点，然后快慢指针同时后移，判断是否相同，如果出现了不相同那么不是回文，否则满足回文条件，得到的代码如下：

附录：源码gitee仓库

    考虑到有些算法需要模拟数据，如果全部放进来代码显得过长，不利于聚焦在算法的核心思路上。于是把所有的代码整理到了开源仓库上，如果想要看详细模拟数据，可在开源仓库自取：【凌空暗羽/剑指offer-C++版手写代码】。

    我是【Jerry说前后端】，本系列精心挑选的算法题目全部基于经典的《剑指 Offer（数据结构与算法面试题精讲）》。在如今竞争激烈的技术求职环境下，算法能力已成为前端开发岗位笔试考核的关键要点。通过深入钻研这一系列算法题，大家能够系统地积累算法知识和解题经验。每一道题目的分析与解答过程，都像是一把钥匙，为大家打开一扇通往高效编程思维的大门，帮助大家逐步提升自己在数据结构运用、算法设计与优化等方面的能力。
    无论是即将踏入职场的应届毕业生，还是想要进一步提升自己技术水平的在职开发者，掌握扎实的算法知识都是提升竞争力的有力武器。希望大家能跟随我的步伐，在这个系列中不断学习、不断进步，为即将到来的前端笔试做好充分准备，顺利拿下心仪的工作机会！快来订阅吧，让我们一起开启这段算法学习之旅！