⭐ 题目日期：

字节 - 秋招二面 2024/10/16

🌳 题目描述：

给定两个 非空链表 l1和 l2 来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一个字符（0 - 9，a - z）。将这两数相加会返回一个新的链表。备注：a 代表 10， b 代表 11，以此类推

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

示例 1：
第一个数：'1' -> 'a' -> 'z' （对应 1az）
第二个数：'2' -> 'b' -> 'y' （对应 2by）
相加得到：'3' -> 'n' -> '5'  (对应 3n5)
示例 2：
第一个数：'9' -> '0' -> '1' （对应 901）
第二个数：'1' -> 'b' -> '3' -> '5' （对应 1b35）
相加得到：'1' -> 'k' -> '3' -> '6'  (对应 1k36)

🧗难度系数：

⭐️ ⭐️ ⭐️️

📝思路分析：

根据题意，高位靠近表头，而加法规则需要低位对齐：

🌟 方法一：

反转链表，实现低位对齐

原链表：

第一个数：'9' -> '0' -> '1' （对应 901）

第二个数：'1' -> 'b' -> '3' -> '5' （对应 1b35）

反转之后：

第一个数：'1' -> '0' -> '9'

第二个数：'5' -> '3' -> 'b' -> '1'

相加：'6' -> '3' -> 'k' ->'1', 再将结果反转得：'1' -> 'k' -> '3' -> '6'

💻代码：

Java

class ListNode {
 char val;
 ListNode next;
 ListNode(char val) {
     this.val = val;
 }
}

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
 // 反转链表
 l1 = reverseList(l1);
 l2 = reverseList(l2);

 ListNode dummyHead = new ListNode('0');
 ListNode current = dummyHead;
 int carry = 0;

 // 逐位相加
 while (l1 != null || l2 != null || carry != 0) {
     int x = l1 != null ? charToInt(l1.val) : 0;
     int y = l2 != null ? charToInt(l2.val) : 0;
     int sum = x + y + carry;
     carry = sum / 32;
     sum = sum % 32;

     current.next = new ListNode(intToChar(sum));
     current = current.next;

     if (l1 != null) {
         l1 = l1.next;
     } 

     if (l2 != null) {
         l2 = l2.next;
     }
 }

 // 结果链表反转
 return reverseList(dummyHead.next);
}

// 将字符数字映射为整数值
private int charToInt(char c) {
 if (c <= '9') {
     return c - '0';
 } else {
     return c - 'a' + 10;
 }
}

// 将小于32的整数值映射为字符数字
private char intToChar(int num) {
 if (num <= 9) {
     return (char) ('0' + num);
 } else {
     return (char) ('a' + num - 10);
 }
}

private ListNode reverseList(ListNode head) {
 ListNode prev = null;
 while (head != null) {
     ListNode next = head.next;
     head.next = prev;
     prev = head;
     head = next;
 }
 return prev;
}

🚵🏻复杂度分析：

时间复杂度：O(m + n)

空间复杂度：O(1)

🌟 方法二：

避免直接操作链表，引入栈

根据栈的先入后出的特性，从链表头节点开始将所有节点入栈，这样低位在栈顶，可以依次出栈计算。

💻代码：

Java

class ListNode {
 char val;
 ListNode next;
 ListNode(char val) {
     this.val = val;
 }
}

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
 // 初始化两个栈
 Deque<Integer> stack1 = new LinkedList<>();
 Deque<Integer> stack2 = new LinkedList<>();

 // 将链表节点值压入栈中
 while (l1 != null) {
     stack1.push(charToInt(l1.val));
     l1 = l1.next;
 }

 while (l2 != null) {
     stack2.push(charToInt(l2.val));
     l2 = l2.next;
 }

 int carry = 0;
 ListNode pre = null; 

 // 逐位相加
 while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {
     int x = !stack1.isEmpty() ? stack1.pop() : 0;
     int y = !stack2.isEmpty() ? stack2.pop() : 0;
     int sum = x + y + carry;
     carry = sum / 32;
     sum = sum % 32;

     // 创建新节点，插入到链表头部
     ListNode head = new ListNode(intToChar(sum));
     head.next = pre;
     pre = head;
 }

 return pre;
}

// 将字符数字映射为整数值
private int charToInt(char c) {
 if (c <= '9') {
     return c - '0';
 } else {
     return c - 'a' + 10;
 }
}

// 将小于32的整数值映射为字符数字
private char intToChar(int num) {
 if (num <= 9) {
     return (char) ('0' + num);
 } else {
     return (char) ('a' + num - 10);
 }
}

🚵🏻复杂度分析：

时间复杂度：O(m + n)

空间复杂度：O(m + n)

题目链接