题解 | 链表相加(二)

1、解题思路

1. 反转链表：由于加法是从最低位开始计算，因此需要先将两个链表反转，以便从低位到高位依次相加。
2. 相加处理：同时遍历两个反转后的链表，逐位相加，并处理进位。如果某个链表遍历完毕，则剩余部分直接与进位相加。如果最后还有进位，需要额外创建一个节点。
3. 反转结果链表：将相加得到的结果链表反转，恢复成高位在前、低位在后的顺序。

2、代码实现

C++

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        // 反转两个链表以便从低位开始相加
        ListNode* cur1 = reverseList(head1);
        ListNode* cur2 = reverseList(head2);

        ListNode dummy(0), *cur = &dummy;
        int carry = 0;  // 进位初始化为 0

        // 同时遍历两个链表
        while (cur1 || cur2 || carry) {
            if (cur1) {
                carry += cur1->val;
                cur1 = cur1->next;
            }
            if (cur2) {
                carry += cur2->val;
                cur2 = cur2->next;
            }

            cur->next = new ListNode(carry % 10);
            carry /= 10;
            cur = cur->next;
        }

        // 反转结果链表
        cur = reverseList(dummy.next);
        return cur;
    }

  private:
    // 反转链表函数
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr, *cur = head;
        while (cur) {
            ListNode* next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
};

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
        // 反转链表以便从低位开始相加
        ListNode cur1 = reverseList(head1);
        ListNode cur2 = reverseList(head2);

        ListNode dummy = new ListNode(-1); // 虚拟头节点
        ListNode curr = dummy;
        int carry = 0; // 进位初始为0

        // 同时遍历两个链表
        while (cur1 != null || cur2 != null || carry != 0) {
            if (cur1 != null) {
                carry += cur1.val;
                cur1 = cur1.next;
            }
            if (cur2 != null) {
                carry += cur2.val;
                cur2 = cur2.next;
            }

            curr.next = new ListNode(carry % 10); // 当前位的值
            carry = carry / 10; // 计算进位
            curr = curr.next;
        }

        // 反转结果链表
        curr = reverseList(dummy.next);
        return curr;
    }

    // 反转链表函数
    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

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
        # 反转链表以便从低位开始相加
        cur1 = self.reverseList(head1)
        cur2 = self.reverseList(head2)

        dummy = ListNode(-1)  # 虚拟头节点
        curr = dummy
        carry = 0  # 进位初始为0

        # 同时遍历两个链表
        while cur1 or cur2 or carry:
            if cur1:
                carry += cur1.val
                cur1 = cur1.next
            if cur2:
                carry += cur2.val
                cur2 = cur2.next

            curr.next = ListNode(carry % 10)  # 当前位的值
            carry = carry // 10  # 计算进位
            curr = curr.next

        # 反转结果链表
        result = self.reverseList(dummy.next)
        return result

    # 反转链表函数
    def reverseList(self, head: ListNode) -> ListNode:
        prev = None
        curr = head
        while curr:
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node
        return prev

3、复杂度分析

• 时间复杂度：O(n)。
• 空间复杂度：O(1)。