Location>code7788 >text

[Ninja Algorithm] From Life to Code: A wonderful algorithm for decrypting the addition of large numbers on linked lists | LeetCode Question 2 "Add two numbers"

Popularity：111 ℃/2025-02-21 20:48:31

From life to code: A wonderful algorithm for decrypting the number addition of large numbers on linked lists

Start with the supermarket cashier

Imagine you are a supermarket cashier calculating the sum of shopping for two customers. Each customer's products are placed in order from single to high (for example, 54 yuan means 4 yuan first, and 50 yuan products). You need to add up one by one, and if you encounter more than 10 yuan, you will carry it. This scenario is exactly the true portrayal of the problem of adding two numbers in the linked list that we are going to solve today.

Problem description

LeetCode Question 2 "Add two numbers" requirements: Give you two non-empty linked lists to represent two non-negative integers. They store a number per node and are stored in reverse order. Please add these two numbers and return a linked list representing the sum in the same form.

For example:

Enter: 2 → 4 → 3, 5 → 6 → 4
 Explanation: 342 + 465 = 807
 Output: 7 → 0 → 8

 Enter: 9 → 9 → 9, 1
 Explanation: 999 + 1 = 1000
 Output: 0 → 0 → 0 → 1

 Input: 0, 0
 Output: 0

Idea Analysis: Simulated Manual Algorithm Addition

Just like we do addition on paper:

  1. Starting from the lowest point, two numbers are added together
  2. If the sum exceeds 10, carry is required
  3. The carry 1 should be added to the next bit calculation

This process is perfectly mapped to the traversal of linked lists: start from the first node (single bits), traverse two linked lists at the same time, and handle the carry relationship well.

Code implementation and detailed explanation

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
     // Create sentinel nodes to simplify processing of head nodes
     ListNode dummy = new ListNode(0);
     ListNode current = dummy;
    
     // carry means carry value, initially 0
     int carry = 0;
    
     // As long as there are numbers to add, continue to loop
     while (l1 != null || l2 != null || carry > 0) {
         // Get the value of the current bit, if the linked list has been traversed, add 0
         int val1 = (l1 != null) ? : 0;
         int val2 = (l2 != null) ? : 0;
        
         // Calculate the sum of the current bit, including the carry of the previous bit
         int sum = val1 + val2 + carry;
        
         // Calculate the new carry value
         carry = sum / 10;
        
         // Create a new node and store the results of the current bit
          = new ListNode(sum % 10);
         current = ;
        
         // Move to the next
         l1 = (l1 != null) ? : null;
         l2 = (l2 != null) ? : null;
     }
    
     return ;
 }

Graphical process

Example: 342 + 465 = 807
 1) Initial status:
 l1: 2 → 4 → 3
 l2: 5 → 6 → 4
 sum: dummy →

 2) Processing single digits: 2 + 5 = 7
 l1: 4 → 3
 l2: 6 → 4
 sum: dummy → 7 →

 3) Processing ten digits: 4 + 6 = 10
 l1: 3
 l2: 4
 sum: dummy → 7 → 0 → (carry=1)

 4) Processing hundreds of digits: 3 + 4 + 1 (carry) = 8
 sum: dummy → 7 → 0 → 8

Special circumstances handling

This solution gracefully handles all special cases:

  1. The two linked lists have different lengths

    • While condition contains checks for two linked lists
    • Short link lists are filled with 0

  2. Highest carry

    • carry > 0 guarantees that the last carry will be processed
    • For example: 999 + 1 = 1000

  3. Empty link table

    • The initial sentinel node ensures that the result list is always valid

Implement details and optimization

  1. Time complexity: O(max(N, M))

    • N and M are the lengths of two linked lists
    • Just traverse the longest linked list once

  2. Space complexity: O(max(N, M))

    • Need to store the result link table
    • The result has a maximum length of 1 bit more than the longest input (caused by carriage)

  3. Code optimization tips:

    • Simplify head node processing using sentinel nodes
    • Unified processing of carry and numeric addition
    • Elegantly handle different lengths

Thinking about practical application

The idea of ​​this algorithm is applied in many scenarios:

  1. Large number calculation

    • Handle numbers beyond the range of language built-in data types
    • Accurate calculations in the financial system

  2. Data flow processing

    • Streaming large amounts of data
    • Real-time computing system

  3. Priority conversion

    • The idea of ​​analog carry can be used for the primary conversion
    • Processing operations of different digits

Expand and enhance

  1. How to deal with negative numbers?

    • Sign bits can be added
    • Addition of different symbols and numbers needs to be considered

  2. How to deal with numbers stored in positive order?

    • You can reverse the link list first
    • Or use the stack to store nodes

summary

The problem of adding two numbers in the linked list tells us:

  1. Complex problems can be simplified by simulating manual solutions
  2. A good code structure can handle various boundary situations gracefully
  3. The choice of data structure affects the solution to the problem

Warm reminder: When dealing with similar problems, first think about how people solve it, and then convert this process into code, which can often lead to clearer ideas.

Author: Ninja Algorithm
Official account: Ninja Algorithm

I have prepared a list of questions to practice and detailed questions for these questions, covering most common interview questions. I can say responsibly that as long as you truly master these questions, 80% of the algorithm interviews will encounter similar questions. Reply to the official account [Question List] to obtain ~

<Previous Next>