一、面试问题一个数字以链表形式存储每位数字对应链表中的一个节点。任务是给这个数字加 1。示例 1输入链表头节点4 - 5 - 6输出链表头节点4 - 5 - 7解释对链表所表示的数字加 1即 456 1 457。示例 2输入头节点链表2 - 1 - 6 - 9输出头节点链表2 - 1 - 7 - 0解释将链表表示的数字加 1即 2169 1 2170。二、【解法-1】递归法 —— 时间复杂度 O (n)空间复杂度 O (n)(一) 解法思路递归遍历链表先走到最后一个节点。这样可以优先处理最低位数字。给最后一个节点的值加 1并计算本次加法产生的进位。回溯过程中根据后一个节点传递过来的进位依次更新每个节点的值。遍历结束后若进位不为 0则新建一个以进位值为数据的节点插入到链表头部。(二) 使用 6 种语言实现1. C// C 程序使用递归法给链表表示的数字加 1 #include iostream using namespace std; // 链表节点类 class Node { public: int data; Node *next; // 构造函数创建新节点 Node(int x) { data x; next nullptr; } }; // 递归函数从链表尾部向头部依次加1并返回进位 int addWithCarry(Node *head) { // 递归终止条件链表为空返回进位 1因为我们要 1 if (head nullptr) { return 1; } // 递归调用下一个节点接收返回的进位并与当前节点值相加 int res head-data addWithCarry(head-next); // 更新当前节点的值取个位 head-data res % 10; // 返回新的进位取十位 return res / 10; } // 主函数给链表数字加 1 Node *addOne(Node *head) { // 调用递归函数处理所有节点并获取最终进位 int carry addWithCarry(head); // 如果最终还有进位如 999 - 1000新建节点插入到头部 if (carry) { Node *newNode new Node(carry); newNode-next head; // 新节点成为新的头节点 return newNode; } return head; } // 打印链表 void printList(Node *head) { Node *curr head; while (curr ! nullptr) { cout curr-data ; curr curr-next; } cout endl; } // 主函数测试 int main() { // 创建链表: 1 - 9 - 9 - 9 表示数字 1999 Node *head new Node(1); head-next new Node(9); head-next-next new Node(9); head-next-next-next new Node(9); // 给链表数字 1 head addOne(head); // 打印结果2 0 0 0 printList(head); return 0; }2. C// C 程序给链表表示的数字加 1 #include stdio.h #include stdlib.h struct Node { int data; struct Node* next; }; struct Node* createNode(int data); // 递归地从尾部向头部加 1并处理完所有节点后返回进位 int addWithCarry(struct Node* head) { // 如果链表为空返回进位 1 if (head NULL) { return 1; } // 加上下一个节点调用返回的进位 int res head-data addWithCarry(head-next); // 更新数据并返回新的进位 head-data res % 10; return res / 10; } struct Node* addOne(struct Node* head) { // 从尾部向头部给链表加 1 int carry addWithCarry(head); // 如果更新所有节点后仍有进位则需要向链表添加一个新节点 if (carry) { struct Node* newNode createNode(carry); newNode-next head; // 新节点成为新的头节点 return newNode; } return head; } void printList(struct Node* head) { struct Node* curr head; while (curr ! NULL) { printf(%d , curr-data); curr curr-next; } printf(\n); } struct Node* createNode(int data) { struct Node* newNode (struct Node*)malloc(sizeof(struct Node)); newNode-data data; newNode-next NULL; return newNode; } int main() { // 创建一个硬编码的链表 // 1 - 9 - 9 - 9 struct Node* head createNode(1); head-next createNode(9); head-next-next createNode(9); head-next-next-next createNode(9); head addOne(head); printList(head); return 0; }3. Java// Java 程序给链表表示的数字加 1 class Node { int data; Node next; Node(int data) { this.data data; this.next null; } } // 递归地从尾部向头部加 1并处理完所有节点后返回进位 class DSA { static int addWithCarry(Node head) { // 如果链表为空返回进位 1 if (head null) { return 1; } // 加上下一个节点调用返回的进位 int res head.data addWithCarry(head.next); // 更新数据并返回新的进位 head.data res % 10; return res / 10; } static Node addOne(Node head) { // 从尾部向头部给链表加 1 int carry addWithCarry(head); // 如果更新所有节点后仍有进位则需要向链表添加一个新节点 if (carry 0) { Node newNode new Node(carry); newNode.next head; // 新节点成为新的头节点 return newNode; } return head; } static void printList(Node head) { Node curr head; while (curr ! null) { System.out.print(curr.data ); curr curr.next; } System.out.println(); } public static void main(String[] args) { // 创建一个硬编码的链表 // 1 - 9 - 9 - 9 Node head new Node(1); head.next new Node(9); head.next.next new Node(9); head.next.next.next new Node(9); head addOne(head); printList(head); } }4. Python# Python 程序给链表表示的数字加 1 class Node: def __init__(self, data): self.data data self.next None # 递归地从尾部向头部加 1并处理完所有节点后返回进位 def addWithCarry(head): # 如果链表为空返回进位 1 if head is None: return 1 # 加上下一个节点调用返回的进位 res head.data addWithCarry(head.next) # 更新数据并返回新的进位 head.data res % 10 return res // 10 def addOne(head): # 从尾部向头部给链表加 1 carry addWithCarry(head) # 如果更新所有节点后仍有进位则需要向链表添加一个新节点 if carry: newNode Node(carry) newNode.next head # 新节点成为新的头节点 return newNode return head def printList(head): curr head while curr: print(curr.data, end ) curr curr.next print() if __name__ __main__: # 创建一个硬编码的链表 # 1 - 9 - 9 - 9 head Node(1) head.next Node(9) head.next.next Node(9) head.next.next.next Node(9) head addOne(head) printList(head)5. C#// C# 程序给链表表示的数字加 1 using System; class Node { public int data; public Node next; public Node(int data) { this.data data; this.next null; } } class DSA { // 递归地从尾部向头部加 1并处理完所有节点后返回进位 static int addWithCarry(Node head) { // 如果链表为空返回进位 1 if (head null) { return 1; } // 加上下一个节点调用返回的进位 int res head.data addWithCarry(head.next); // 更新数据并返回新的进位 head.data res % 10; return res / 10; } static Node addOne(Node head) { // 从尾部向头部给链表加 1 int carry addWithCarry(head); // 如果更新所有节点后仍有进位则需要向链表添加一个新节点 if (carry 0) { Node newNode new Node(carry); newNode.next head; // 新节点成为新的头节点 return newNode; } return head; } static void printList(Node head) { Node curr head; while (curr ! null) { Console.Write(curr.data ); curr curr.next; } Console.WriteLine(); } static void Main() { // 创建一个硬编码的链表 // 1 - 9 - 9 - 9 Node head new Node(1); head.next new Node(9); head.next.next new Node(9); head.next.next.next new Node(9); head addOne(head); printList(head); } }6. JavaScript// Javascript 程序给链表表示的数字加 1 class Node { constructor(data) { this.data data; this.next null; } } // 递归地从尾部向头部加 1并处理完所有节点后返回进位 function addWithCarry(head) { // 如果链表为空返回进位 1 if (head null) { return 1; } // 加上下一个节点调用返回的进位 const res head.data addWithCarry(head.next); // 更新数据并返回新的进位 head.data res % 10; return Math.floor(res / 10); } function addOne(head) { // 从尾部向头部给链表加 1 const carry addWithCarry(head); // 如果更新所有节点后仍有进位则需要向链表添加一个新节点 if (carry 0) { const newNode new Node(carry); newNode.next head; // 新节点成为新的头节点 return newNode; } return head; } function printList(head) { let curr head; while (curr ! null) { console.log(curr.data ); curr curr.next; } console.log(); } // 创建一个硬编码的链表 // 1 - 9 - 9 - 9 let head new Node(1); head.next new Node(9); head.next.next new Node(9); head.next.next.next new Node(9); head addOne(head); printList(head);(三)代码输出和算法复杂度输出2 0 0 0时间复杂度O(n)。空间复杂度O(n)。三、【解法-2】迭代法 —— 时间复杂度 O (n)空间复杂度 O (1)(一) 解法思路反转给定的链表。例如1-9-9-9 反转为 9-9-9-1。从最左侧的节点开始遍历链表并给它加 1。如果存在进位则移动到下一个节点。只要有进位就继续移动到下一个节点。这一步得到 0-0-0-2。遍历结束后如果进位不等于 0则创建一个以进位值为数据的新节点并将其插入到头部。在本例中进位为 0。反转修改后的链表并返回头节点。最终得到 2-0-0-0。(二) 使用 6 种语言实现1. C// C 程序给链表表示的数字加 1 #include bits/stdc.h using namespace std; class Node { public: int data; Node *next; Node(int x) { data x; next nullptr; } }; // 反转链表的函数 Node* reverse(Node* head) { Node *curr head, *prev nullptr, *next; while (curr ! nullptr) { next curr-next; curr-next prev; prev curr; curr next; } return prev; } // 给链表加 1 并返回结果链表头节点的函数 Node *addOneUtil(Node *head) { Node *res head; Node *curr head; Node *last nullptr; // 初始化进位为 1用于加 1 int carry 1; int sum; while (curr ! nullptr) { // 计算进位与当前节点数据的和 sum carry curr-data; // 更新下一位的进位 carry (sum 10) ? 1 : 0; // 将当前节点数据更新为和对 10 取模 curr-data sum % 10; // 移动到下一个节点 last curr; curr curr-next; } // 如果仍有剩余进位添加一个携带进位值的新节点 if (carry 0) { last-next new Node(carry); } return res; } // 给链表加 1 的主函数 Node *addOne(Node *head) { // 反转链表 head reverse(head); // 给反转后的链表加 1 head addOneUtil(head); // 再次反转链表恢复原始顺序 return reverse(head); } void printList(Node *head) { Node *curr head; while (curr ! nullptr) { cout curr-data ; curr curr-next; } cout endl; } int main() { // 创建一个硬编码的链表 // 1 - 9 - 9 - 9 Node *head new Node(1); head-next new Node(9); head-next-next new Node(9); head-next-next-next new Node(9); head addOne(head); printList(head); return 0; }2. C// C 程序给链表表示的数字加 1 #include stdio.h #include stdlib.h struct Node { int data; struct Node* next; }; struct Node* createNode(int data); // 反转链表的函数 struct Node* reverse(struct Node* head) { struct Node* curr head; struct Node* prev NULL; struct Node* next; while (curr ! NULL) { next curr-next; curr-next prev; prev curr; curr next; } return prev; } // 给链表加 1 并返回结果链表头节点的函数 struct Node* addOneUtil(struct Node* head) { struct Node* res head; struct Node* curr head; struct Node* last NULL; // 初始化进位为 1用于加 1 int carry 1; int sum; while (curr ! NULL) { // 计算进位与当前节点数据的和 sum carry curr-data; // 更新下一位的进位 carry (sum 10) ? 1 : 0; // 将当前节点数据更新为和对 10 取模 curr-data sum % 10; // 移动到下一个节点 last curr; curr curr-next; } // 如果仍有剩余进位添加一个携带进位值的新节点 if (carry 0) { last-next createNode(carry); } return res; } // 给链表加 1 的主函数 struct Node* addOne(struct Node* head) { // 反转链表 head reverse(head); // 给反转后的链表加 1 head addOneUtil(head); // 再次反转链表恢复原始顺序 return reverse(head); } void printList(struct Node* head) { struct Node* curr head; while (curr ! NULL) { printf(%d , curr-data); curr curr-next; } printf(\n); } struct Node* createNode(int data) { struct Node* newNode (struct Node*)malloc(sizeof(struct Node)); newNode-data data; newNode-next NULL; return newNode; } int main() { // 创建一个硬编码的链表 // 1 - 9 - 9 - 9 struct Node* head createNode(1); head-next createNode(9); head-next-next createNode(9); head-next-next-next createNode(9); head addOne(head); printList(head); return 0; }3. Java// Java 程序给链表表示的数字加 1 class Node { int data; Node next; Node(int x) { this.data x; this.next null; } } // 反转链表的函数 class DSA { static Node reverse(Node head) { Node curr head, prev null, next; while (curr ! null) { next curr.next; curr.next prev; prev curr; curr next; } return prev; } // 给链表加 1 并返回结果链表头节点的函数 static Node addOneUtil(Node head) { Node res head; Node curr head; Node last null; // 初始化进位为 1用于加 1 int carry 1; int sum; while (curr ! null) { // 计算进位与当前节点数据的和 sum carry curr.data; // 更新下一位的进位 carry (sum 10) ? 1 : 0; // 将当前节点数据更新为和对 10 取模 curr.data sum % 10; // 移动到下一个节点 last curr; curr curr.next; } // 如果仍有剩余进位添加一个携带进位值的新节点 if (carry 0) { last.next new Node(carry); } return res; } // 给链表加 1 的主函数 static Node addOne(Node head) { // 反转链表 head reverse(head); // 给反转后的链表加 1 head addOneUtil(head); // 再次反转链表恢复原始顺序 return reverse(head); } static void printList(Node head) { Node curr head; while (curr ! null) { System.out.print(curr.data ); curr curr.next; } System.out.println(); } public static void main(String[] args) { // 创建一个硬编码的链表 // 1 - 9 - 9 - 9 Node head new Node(1); head.next new Node(9); head.next.next new Node(9); head.next.next.next new Node(9); head addOne(head); printList(head); } }4. Python# Python3 程序给链表表示的数字加 1 class Node: def __init__(self, data): self.data data self.next None # 反转链表的函数 def reverse(head): curr head prev None while curr: next curr.next curr.next prev prev curr curr next return prev # 给链表加 1 并返回结果链表头节点的函数 def addOneUtil(head): res head curr head last None # 初始化进位为 1用于加 1 carry 1 while curr: # 计算进位与当前节点数据的和 sum carry curr.data # 更新下一位的进位 carry 1 if sum 10 else 0 # 将当前节点数据更新为和对 10 取模 curr.data sum % 10 # 移动到下一个节点 last curr curr curr.next # 如果仍有剩余进位添加一个携带进位值的新节点 if carry 0: last.next Node(carry) return res # 给链表加 1 的主函数 def addOne(head): # 反转链表 head reverse(head) # 给反转后的链表加 1 head addOneUtil(head) # 再次反转链表恢复原始顺序 return reverse(head) def printList(head): curr head while curr: print(curr.data, end ) curr curr.next print() if __name__ __main__: # 创建一个硬编码的链表 # 1 - 9 - 9 - 9 head Node(1) head.next Node(9) head.next.next Node(9) head.next.next.next Node(9) head addOne(head) printList(head)5. C#// C# 程序给链表表示的数字加 1 using System; class Node { public int data; public Node next; public Node(int x) { this.data x; this.next null; } } class DSA { // 反转链表的函数 static Node Reverse(Node head) { Node curr head, prev null, next null; while (curr ! null) { next curr.next; curr.next prev; prev curr; curr next; } return prev; } // 给链表加 1 并返回结果链表头节点的函数 static Node AddOneUtil(Node head) { Node res head; Node curr head; Node last null; // 初始化进位为 1用于加 1 int carry 1; int sum; while (curr ! null) { // 计算进位与当前节点数据的和 sum carry curr.data; // 更新下一位的进位 carry (sum 10) ? 1 : 0; // 将当前节点数据更新为和对 10 取模 curr.data sum % 10; // 移动到下一个节点 last curr; curr curr.next; } // 如果仍有剩余进位添加一个携带进位值的新节点 if (carry 0) { last.next new Node(carry); } return res; } // 给链表加 1 的主函数 static Node AddOne(Node head) { // 反转链表 head Reverse(head); // 给反转后的链表加 1 head AddOneUtil(head); // 再次反转链表恢复原始顺序 return Reverse(head); } static void PrintList(Node head) { Node curr head; while (curr ! null) { Console.Write(curr.data ); curr curr.next; } Console.WriteLine(); } static void Main() { // 创建一个硬编码的链表 // 1 - 9 - 9 - 9 Node head new Node(1); head.next new Node(9); head.next.next new Node(9); head.next.next.next new Node(9); head AddOne(head); PrintList(head); } }6. JavaScript// Javascript 程序给链表表示的数字加 1 class Node { constructor(data) { this.data data; this.next null; } } // 反转链表的函数 function reverse(head) { let curr head, prev null, next; while (curr ! null) { next curr.next; curr.next prev; prev curr; curr next; } return prev; } // 给链表加 1 并返回结果链表头节点的函数 function addOneUtil(head) { let res head; let curr head; let last null; // 初始化进位为 1用于加 1 let carry 1; let sum; while (curr ! null) { // 计算进位与当前节点数据的和 sum carry curr.data; // 更新下一位的进位 carry (sum 10) ? 1 : 0; // 将当前节点数据更新为和对 10 取模 curr.data sum % 10; // 移动到下一个节点 last curr; curr curr.next; } // 如果仍有剩余进位添加一个携带进位值的新节点 if (carry 0) { last.next new Node(carry); } return res; } // 给链表加 1 的主函数 function addOne(head) { // 反转链表 head reverse(head); // 给反转后的链表加 1 head addOneUtil(head); // 再次反转链表恢复原始顺序 return reverse(head); } function printList(head) { let curr head; while (curr ! null) { console.log(curr.data ); curr curr.next; } console.log(); } // 创建一个硬编码的链表 // 1 - 9 - 9 - 9 let head new Node(1); head.next new Node(9); head.next.next new Node(9); head.next.next.next new Node(9); head addOne(head); printList(head);(三)代码输出和算法复杂度输出2 0 0 0时间复杂度O(n)。空间复杂度O(1)。