链表加法与节点交换:数据结构的基础技能

淩亂°似流年 2024-02-20 10:00 25阅读 0赞

#### 目录 ####

*   *  两两交换链表中的节点
     *  单链表加一
     *  链表加法
     *   *  使用栈实现
         *  使用链表反转实现

### 两两交换链表中的节点 ###

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。  
![在这里插入图片描述][fe91712d196842a58ba23b8cb233d302.png]

我们依旧使用虚拟头节点来进行交换。  
![在这里插入图片描述][6f3beb4689994da2bdf2d6f4195f527c.png]  
这张图很是清晰的标明了我们要做的交换步骤：

1.  首先，创建一个虚拟头节点dummyHead,并将其next指针指向head。然后定义一个临时变量temp,将其初始化为dummyHead。
2.  使用一个while循环遍历链表，直到遇到链表的末尾(即temp.next或temp.next.next为null)。
3.  在循环中，首先将temp.next赋值给node1,将temp.next.next赋值给node2。然后将temp的next指针指向node2,将node1的next指针指向node2的next,最后将node2的next指针指向node1，然后把temp指向node1。
4.  循环结束后，返回dummyHead.next,即交换后的链表的头节点。

public ListNode swapPairs(ListNode head) {
        
            ListNode dummyHead = new ListNode(-1);
            dummyHead.next = head;
            ListNode temp = dummyHead;
            while (temp.next != null && temp.next.next != null) {
        
                ListNode node1 = temp.next;
                ListNode node2 = temp.next.next;
                temp.next = node2;
                node1.next = node2.next;
                node2.next = node1;
                temp = node1;
            }
            return dummyHead.next;
        }

### 单链表加一 ###

给定一个用单链表表示的整数，然后把这个整数加一。  
![在这里插入图片描述][e8307eeb4fd04fec9b88a32b2fd55f41.png]

public ListNode plusOne(ListNode head) {
        
            Stack<Integer> stack = new Stack<>();
            while (head != null) {
        
                stack.push(head.val);
                head = head.next;
            }
            int carry = 0;
            int adder = 1;
            ListNode dummy = new ListNode(0);
            while (!stack.isEmpty() || carry > 0) {
        
                int digit = stack.isEmpty() ? 0 : stack.pop();
                int sum = digit + carry + adder;
                carry = sum >= 10 ? 1 : 0;
                sum = sum >= 10 ? sum - 10 : sum;
                ListNode node = new ListNode(sum);
                node.next = dummy.next;
                dummy.next = node;
                adder = 0;
            }
            return dummy.next;
        }

我们的实现思路就是先把链表压入栈中，给最低位加一，用carry来记录是否有进位，然后用头插的方式把加一的链表连接起来。

1.  首先创建一个空的栈（Stack）用于保存链表中的数字，并将链表中的每个节点的值依次入栈。
2.  创建两个变量carry（进位）和adder（加法器），初始化carry为0， adder为1。
3.  创建一个虚拟节点dummy，并将其值设置为0。用于存储相加后的链表。
4.  进入while循环，直到栈为空且没有进位时结束循环。在每次循环中，我们从栈中弹出一个数字digit，并计算和sum = digit + carry + adder。
5.  判断sum是否大于等于10，如果是，设置carry为1（表示进位），并将sum减去10。否则，carry为0。
6.  创建一个新的节点node，值为sum，并将node插入到虚拟节点dummy之后。
7.  继续进行下一次循环之前，将adder设为0，以确保下次循环只进行加法操作。
8.  返回虚拟节点dummy的下一个节点，即加法操作完成后的链表头节点。

### 链表加法 ###

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

![在这里插入图片描述][3befd2d690014447837d163230ce57d7.png]  
我们用两种方式来实现：

#### 使用栈实现 ####

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        
            Stack<ListNode> stack1 = new Stack<>();
            Stack<ListNode> stack2 = new Stack<>();
            while (l1 != null) {
        
                stack1.push(l1);
                l1 = l1.next;
            }
            while (l2 != null) {
        
                stack2.push(l2);
                l2 = l2.next;
            }
            ListNode dummy = new ListNode(-1);
            int carry = 0;
            while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {
        
                ListNode a = new ListNode(0);
                ListNode b = new ListNode(0);
                if (!stack1.isEmpty()) {
        
                    a.val = stack1.pop().val;
                }
                if (!stack2.isEmpty()) {
        
                    b.val = stack2.pop().val;
                }
                int sum = carry + a.val + b.val;
                int ans = sum % 10;
                carry = sum / 10;
                ListNode cur = new ListNode(ans);
                cur.next = dummy.next;
                dummy.next = cur;
            }
            return dummy.next;
        }

以上代码实现了两个链表的加法操作。

1.  首先创建两个栈stack1和stack2，分别用于存储链表l1和l2中的节点。
2.  使用while循环，将链表l1和l2的节点依次入栈到stack1和stack2中。
3.  创建一个虚拟节点dummy，并将其值设为-1，用于存储相加后的链表。
4.  创建一个变量carry用于表示进位，初始值为0。
5.  进入while循环，条件为stack1或stack2不为空，或者carry不为0。在每次循环中，我们从stack1和stack2中弹出当前节点的值。
6.  创建两个新的节点a和b，并将它们的值设为stack1和stack2弹出的节点值。
7.  计算和sum = carry + a.val + b.val，以及当前节点的值ans = sum % 10。
8.  更新进位carry = sum / 10。
9.  创建一个新的节点cur，将其值设为ans，并将cur插入到虚拟节点dummy之后。
10. 继续进行下一次循环，直到stack1、stack2为空且carry为0。
11. 返回虚拟节点dummy的下一个节点，即加法操作完成后的链表头节点。

#### 使用链表反转实现 ####

先将两个链表反转，然后计算结果之后，将结果进行反转。

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        
            l1 = reverse(l1);
            l2 = reverse(l2);
            ListNode head = new ListNode(-1);
            ListNode cur = head;
            int carry = 0;
            while (l1 != null || l2 != null) {
        
                int val = carry;
                if (l1 != null) {
        
                    val += l1.val;
                    l1 = l1.next;
                }
                if (l2 != null) {
        
                    val += l2.val;
                    l2 = l2.next;
                }
                cur.next = new ListNode(val % 10);
                carry = val / 10;
                cur = cur.next;
            }
            if (carry > 0) {
        
                cur.next = new ListNode(carry);
            }
            return reverse(head.next);
        }
    
        public ListNode reverse(ListNode head) {
        
            ListNode cur = head;
            ListNode pre = null;
            while (cur != null) {
        
                ListNode next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
            return pre;
        }

具体来说：

1.  首先，将两个输入的链表l1和l2分别进行倒序处理，即反转链表。
2.  创建一个新的虚拟头节点`head`，并创建一个指针`cur`来表示当前节点，初始时指向`head`。
3.  创建一个变量`carry`来表示进位，初始值为0。
4.  进入循环，直到l1和l2都为空为止。在每次循环中，计算当前位的值`val`，并将`carry`加上对应位的值。
5.  如果l1不为空，将l1的值加到`val`上，并将l1指向下一个节点。
6.  如果l2不为空，将l2的值加到`val`上，并将l2指向下一个节点。
7.  创建一个新的节点`newNode`，其值为`val % 10`，并将其插入到新链表中的下一个位置。
8.  更新`carry`为`val / 10`。
9.  更新当前节点`cur`为新插入的节点。
10. 继续进行下一次循环。
11. 如果最后还有进位，创建一个值为进位的新节点，并将其插入到新链表末尾。
12. 将新链表进行反转，返回反转后的头节点。

这样，两个链表的倒序加法操作就完成了。

[fe91712d196842a58ba23b8cb233d302.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/7728103589974b2b9ec05cd0c5c0d915.png
[6f3beb4689994da2bdf2d6f4195f527c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/cc6e3dec1a65439e9fd5dcb063f0dc0a.png
[e8307eeb4fd04fec9b88a32b2fd55f41.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/6e6d8b63c4ae4c84b3d88d0f9bf50fe1.png
[3befd2d690014447837d163230ce57d7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/ee34db2cc14346ecac6922006f624f08.png

发表评论取消回复

表情：

评论列表（有 0 条评论，25人围观）

还没有评论，来说两句吧...

相关阅读

相关两两交换链表中的节点

[题目：给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。][Link 1] > 解题思路：

不念不忘少年蓝@/ 2024年03月08日 08:53/ 0 赞/ 76 阅读

相关 LeetCode_节点交换_简单_237.删除链表中的节点

目录 1.题目 2.思路 3.代码实现（Java） 1.题目请编写一个函数，用于删除单链表中某个特定节点。在设计函数时需要注意，你无法访问链

╰半夏微凉°/ 2023年10月06日 22:57/ 0 赞/ 20 阅读

相关 1721. 交换链表中的节点

给你链表的头节点 `head` 和一个整数 `k` 。交换链表正数第 `k` 个节点和倒数第 `k` 个节点的值后，返回链表的头节点（链表从 1 开始索引）。示例

朱雀/ 2023年10月05日 21:25/ 0 赞/ 7 阅读

相关【数据结构】链表：LeetCode题（一）206.反转链表，24.两两交换相邻节点

在讲解链表的LeetCode题之前先说几点注意： head指针与p指针： head 指针指向参数链表的头，用于标识链表 p 指针一

女爷i/ 2022年12月09日 13:59/ 0 赞/ 152 阅读

相关 [数据结构与算法]删除链表节点

递归写法: / @param {ListNode} head @param {number} val @return {ListNode} / var

淡淡的烟草味﹌/ 2022年12月06日 04:27/ 0 赞/ 177 阅读

相关 leetcode1721. 交换链表中的节点

给你链表的头节点 head 和一个整数 k 。交换链表正数第 k 个节点和倒数第 k 个节点的值后，返回链表的头节点（链表从 1 开始索引）。示例 1：输

末蓝、/ 2022年11月06日 01:59/ 0 赞/ 7 阅读

相关 c语言链表排序交换节点的思想,链表的排序（交换指针指向）

本学期c语言实习，要用到链表的排序。虽说以前没用过，但还是花时间写了写。老师说排序的时候指针不变交换节点里面的元素，我觉得这道不如交换指针的指向来的干脆，因为如果按老师的方法来

傷城~/ 2022年10月15日 01:59/ 0 赞/ 159 阅读

相关数据结构 -- 单链表之删除节点

1. 单链表的创建 2.单链表的节点的删除以下代码在 vs2010 测试通过： include "stdafx.h" include <stdlib.

向右看齐/ 2022年09月20日 15:03/ 0 赞/ 186 阅读

相关链表的排序——冒泡（交换数据与交换指针）

交换数值排序： void sortList(Node head, int len) { for(int i=0; i<len-1; i++)

深碍√TFBOYSˉ_/ 2022年07月14日 00:06/ 0 赞/ 200 阅读

相关【数据结构】多项式乘法与加法（c语言链表实现）

设计函数分别求两个一元多项式的乘积与和。输入格式: 输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过

小咪咪/ 2021年11月17日 00:44/ 0 赞/ 323 阅读