用100道题拿下你的算法面试（链表篇-6）：给链表表示的数字加 1-开发者社区

一、面试问题

一个数字以链表形式存储，每位数字对应链表中的一个节点。任务是给这个数字加 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)