题解 | #链表相加(二)#

秒懂【链表相加】！超清晰图解一步步拆解。链表相加有的时候也叫两数相加。

1.思路

对于给定的两个链表相加，首先是最后两个节点值的相加，接下来是倒数第二节点值的相加，从后向前执行节点值的相加。即：节点7与节点3相加，再执行节点3与节点6相加（还需加上进位数），最后是节点9与进位数的相加。

也就是说链表的遍历是从后向前的，因此需要先对链表进行反转，再进行节点值的相加操作，最后再对新生成的链表反转。

具体步骤如下：

第一步：反转链表。

对两个链表指向反转操作（如果对链表反转不太熟悉，可以参考前面的文章：《可视化图解算法：反转链表》）。

第二步：执行链表节点值相加操作。

在此过程中需要先定义一个虚拟头节点与进位的变量。

节点3与节点6相加，注意进位值carry=1：

h2指向为Null，新链表的节点为：h1指向的值+carry（进位值）：

当h2与h1都指向Null时，需要判断进位值carry是否为0，如果不为0，需要将carry的值单独形成一个节点：

第三步：对新生成的链表反转。

反转之后的链表如下所示：

如果文字描述的不太清楚，你可以参考视频的详细讲解：B站@好易学数据结构

2.代码

2.1 Python代码

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param head1 ListNode类
# @param head2 ListNode类
# @return ListNode类
#
class Solution:
    def addInList(self, head1: ListNode, head2: ListNode) -> ListNode:
        # write code here
        # 0. 当前链表为空，返回另外一个链表
        if head1 is None:
            return head2
        if head2 is None:
            return head1

        # 1. 翻转链表
        h1 = self.reverse(head1)
        h2 = self.reverse(head2)

        # 2. 执行链表节点值相加操作
        tmp_head = ListNode(-1)  # 虚拟临时头节点
        cur = tmp_head  # 衔接两个链表节点值相加形成的链表
        carry = 0  # 进位数
        # 2.1 相加链表节点的值
        while h1 is not None or h2 is not None:
            node_sum = 0
            # 当节点不为空的时候，则需要加上当前节点的值
            if h1 is not None:  # h1指针变量指向的值
                node_sum += h1.val
                h1 = h1.next
            if h2 is not None:
                node_sum += h2.val
                h2 = h2.next
            node_sum += carry  # 上一次计算的进位数
            val = node_sum % 10  # 本次相加结果的值
            carry = node_sum // 10  # 本次相加结果的进位数
            cur.next = ListNode(val)  # 衔接新链表节点
            cur = cur.next
        # 2.2 进位数操作（最后当两条链表都加完的时候，进位不为0的时，进位数需单独形成一个链表节点）
        if carry > 0:
            cur.next = ListNode(carry)
        # 3.翻转节点值相加形成的链表
        new_node = self.reverse(tmp_head.next)
        return new_node

    def reverse(self, head):
        pre = None  # （操作的）前序节点
        cur = head  # （操作的）当前节点
        nxt = head  # （操作的）下一个节点
        while cur:
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt
        return pre

2.2 Java代码

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        // 0. 当前链表为空，返回另外一个链表
        if (head1 == null) {
            return head2;
        }
        if (head2 == null) {
            return head1;
        }

        // 1. 翻转链表
        ListNode h1 = reverse(head1);
        ListNode h2 = reverse(head2);

        // 2. 执行链表节点值相加操作
        ListNode tmpHead = new ListNode(-1); // 虚拟临时头节点
        ListNode cur = tmpHead;  //衔接两个链表节点值相加形成的链表
        int carry = 0; //进位数
        // 2.1 相加链表节点的值
        while (h1 != null || h2 != null) {
            int sum = 0;
            // 当节点不为空的时候，则需要加上当前节点的值
            if (h1 != null) {  //
                sum += h1.val;
                h1 = h1.next;
            }
            if (h2 != null) {  //h2指针变量指向的值
                sum += h2.val;
                h2 = h2.next;
            }
            sum += carry;  //上一次计算的进位数
            int val = sum % 10; // 本次相加结果的值
            carry = sum / 10; // 本次相加结果的进位数

            cur.next = new ListNode(val);
            cur = cur.next;
        }
        // 2.2 进位数操作（最后当两条链表都加完的时候，进位不为0的时，进位数需单独形成一个链表节点）
        if (carry > 0) {
            cur.next = new ListNode(carry);
        }
        // 3. 翻转节点值相加形成的链表
        ListNode newNode = reverse(tmpHead.next);
        return newNode;
    }

    private ListNode reverse(ListNode head) {
        ListNode pre = null;  // （操作的）前序节点
        ListNode cur = head; //（操作的）当前节点
        ListNode nxt = head; //（操作的）下一个节点
        while (cur != null) {
            nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }
}

2.3 Go代码

package main

import . "nc_tools"
/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head1 ListNode类 
 * @param head2 ListNode类 
 * @return ListNode类
*/
func addInList( head1 *ListNode ,  head2 *ListNode ) *ListNode {
    // write code here
    // 0. 当前链表为空，返回另外一个链表
	if head1 == nil {
		return head2
	}
	if head2 == nil {
		return head1
	}

	// 1. 翻转链表
	h1 := reverse(head1)
	h2 := reverse(head2)

	// 2. 执行链表节点值相加操作
	tmpHead := &ListNode{Val: -1} // 虚拟临时头节点
	cur := tmpHead                //衔接两个链表节点值相加形成的链表
	carry := 0                    //进位数
	// 2.1 相加链表节点的值
	for h1 != nil || h2 != nil {
		sum := 0
		// 当节点不为空的时候，则需要加上当前节点的值
		if h1 != nil { //h1指针变量指向的值
			sum += h1.Val
			h1 = h1.Next
		}
		if h2 != nil { //h2指针变量指向的值
			sum += h2.Val
			h2 = h2.Next
		}
		sum += carry //上一次计算的进位数
		// 本次相加结果的值
		val := sum % 10
		// 本次相加结果的进位数（更新进位）
		carry = sum / 10
		// 衔接新链表节点
		cur.Next = &ListNode{Val: val}
		cur = cur.Next
	}
	// 2.2 进位数操作（最后当两条链表都加完的时候，进位不为0的时，进位数需单独形成一个链表节点）
	if carry > 0 {
		cur.Next = &ListNode{Val: carry}
	}
	// 3. 翻转节点值相加形成的链表
	newHead := reverse(tmpHead.Next)
	return newHead
}

func reverse(head *ListNode) *ListNode {
	var pre *ListNode //（操作的）前序节点
	cur := head       //（操作的）当前节点
	nxt := head       //（操作的）下一个节点
	for cur != nil {
		nxt = cur.Next
		cur.Next = pre
		pre = cur
		cur = nxt
	}
	return pre

}

如果上面的代码理解的不是很清楚，你可以参考视频的详细讲解：B站@好易学数据结构