leetcode2：两数相加

题目链接

leetcode

题目描述

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。
假设除了数字 0 之外，这两个数都不会以 0 开头。

C++ 代码

#include <iostream>
#include <vector>
using namespace std;

// 链表结点的定义
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

// 辅助函数：创建链表
ListNode* createList(const vector<int>& nums) {
    ListNode* dummy = new ListNode(-1);
    ListNode* cur = dummy;
    for (int num : nums) {
        cur->next = new ListNode(num);
        cur = cur->next;
    }
    return dummy->next;
}

// 辅助函数：打印链表
void printList(ListNode* head) {
    while (head != nullptr) {
        cout << head->val;
        if (head->next != nullptr) cout << " -> ";
        head = head->next;
    }
    cout << endl;
}

// 辅助函数：释放链表内存
void deleteList(ListNode* head) {
    while (head != nullptr) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }
}

/*
    模拟列竖式做加法：
        1.从最低位至最高位，逐位相加。
            若和大于等于 10，则保留个位数字，同时向前一位进 1。
        2.如果最高位有进位，则在最前面补 1。

    有关链表的题目，常用技巧：
        添加一个虚拟头结点，简化边界的判断。
    
    时间复杂度：O(n)
        其中 n 为链表的长度，遍历链表一次。
    空间复杂度：O(1)
        创建结果链表，注意返回值不计入空间复杂度。    
*/
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(-1);
        ListNode* cur = dummy;
        int carry = 0;
        while (l1 || l2 || carry) {
            int num1 = l1 ? l1->val : 0;
            int num2 = l2 ? l2->val : 0;
            int sum = num1 + num2 + carry;
            // 处理进位
            carry = sum / 10;
            sum = sum % 10;
            // 插入新结点
            cur->next = new ListNode(sum);
            cur = cur->next;
            if (l1) l1 = l1->next;
            if (l2) l2 = l2->next;
        }

        return dummy->next;
    }
};

/*
    思路同上

	逆序存储，直接遍历链表从个位开始，符合计算加法的习惯顺序。
	正序存储，需要翻转链表或使用栈来辅助。
*/
class Solution_1 {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(-1);
        ListNode *p = dummy, *p1 = l1, *p2 = l2;
        int carry = 0;
        while (p1 != nullptr || p2 != nullptr || carry > 0) {
            int val = carry;
            if (p1 != nullptr) {
                val += p1->val;
                p1 = p1->next;
            }
            if (p2 != nullptr) {
                val += p2->val;
                p2 = p2->next;
            }
            // 处理进位
            carry = val / 10;
            val = val % 10;
            // 插入新结点
            p->next = new ListNode(val);
            p = p->next;
        }

        return dummy->next;
    }
};

int main() {
    // 示例输入
    Solution solution;
    vector<int> l1_nums = {2, 4, 3};
    vector<int> l2_nums = {5, 6, 4};

    // 创建链表
    ListNode* l1 = createList(l1_nums);
    ListNode* l2 = createList(l2_nums);

    // 相加操作
    ListNode* result = solution.addTwoNumbers(l1, l2);
    // 打印结果
    cout << "Result: ";
    printList(result);

    // 释放内存
    deleteList(l1);
    deleteList(l2);
    deleteList(result);

    return 0;
}

Golang 代码

package main

import "fmt"

// 定义链表结点
type ListNode struct {
    Val  int
    Next *ListNode
}

// createLinkedList 创建链表
func createLinkedList(values []int) *ListNode {
	if len(values) == 0 {
		return nil
	}
	head := &ListNode{Val: values[0]}
	current := head
	for _, val := range values[1:] {
		current.Next = &ListNode{Val: val}
		current = current.Next
	}
	return head
}

// printLinkedList 打印链表
func printLinkedList(head *ListNode) string {
	var result []int
	for head != nil {
		result = append(result, head.Val)
		head = head.Next
	}
	return fmt.Sprintf("%v", result)
}

/*
    同时遍历两个链表，将对应结点的值相加，并考虑进位。
    用一个新链表来存储结果。

    时间复杂度：O(n)
        其中 m 和 n 分别是两个链表的长度，需要遍历完较长的那个链表。
    空间复杂度：O(1)
        创建结果链表，注意返回值不计入空间复杂度。
*/
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    dummy := &ListNode{}
    cur := dummy
    carry := 0

    for l1 != nil || l2 != nil || carry > 0 {
        sum := 0
        if l1 != nil {
            sum += l1.Val
            l1 = l1.Next
        }
        if l2 != nil {
            sum += l2.Val
            l2 = l2.Next
        }

        sum = sum + carry
        carry = sum / 10
        sum = sum % 10
        cur.Next = &ListNode{Val: sum}
        cur = cur.Next
    }

    return dummy.Next
}

func main() {
    // 测试用例
    testCases := []struct {
        l1      []int
        l2      []int
        expected []int
    }{
        {
            l1:       []int{2,4,3},
            l2:       []int{5,6,4},
            expected: []int{7,0,8},
        },
        {
            l1:       []int{0},
            l2:       []int{0},
            expected: []int{0},
        },
        {
            l1:       []int{9,9,9,9,9,9,9},
            l2:       []int{9,9,9,9},
            expected: []int{8,9,9,9,0,0,0,1},
        },
    }

    for i, tc := range testCases {
        l1 := createLinkedList(tc.l1)
        l2 := createLinkedList(tc.l2)
        fmt.Printf("Test Case %d, Input: l1 = %v, l2 = %v\n", i+1, printLinkedList(l1), printLinkedList(l2))
        result := addTwoNumbers(l1, l2)
		resultStr := printLinkedList(result)
        expectedStr := fmt.Sprintf("%v", tc.expected)
        
        if resultStr == expectedStr {
            fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, resultStr)
        } else {
            fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %v)\n", i+1, resultStr, expectedStr)
        }
    }
}