Linked List - Add Two Numbers

by LauCyun Sep 20,2014 12:58:04 4,840 views

Question

Problem Statement

You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1's digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example

Given 7->1->6 + 5->9->2. That is, 617 + 295.

Return 2->1->9. That is 912.

Given 3->1->5 and 5->9->2, return 8->0->8.

题解

一道看似简单的进位加法题,实则杀机重重,不信你不看答案自己先做做看。

首先由十进制加法可知应该注意进位的处理,但是这道题仅注意到这点就够了吗?还不够!因为两个链表长度有可能不等长!因此这道题的亮点在于边界和异常条件的处理,感谢 @wen 引入的 dummy 节点,处理起来更为优雅!

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

/***
 * Create a new list node.
 * @param val: The value of the new node.
 * @return
 */
struct ListNode *
newNode(const int val) {
    struct ListNode* temp = (struct ListNode*)malloc(sizeof(struct ListNode));
    temp->val = val;
    temp->next = NULL;
    return temp;
}

/***
 * You are given two non-empty linked lists representing two non-negative integers.
 * The digits are stored in reverse order and each of their nodes contain a single digit.
 * Add the two numbers and return it as a linked list.
 * You may assume the two numbers do not contain any leading zero, except the number 0 itself.
 *
 * Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
 * Output: 7 -> 0 -> 8
 *
 * @param l1: linked lists.
 * @param l2: linked lists.
 * @return: a linked lists.
 */
struct ListNode *
addTwoNumbers(struct ListNode *l1, struct ListNode *l2) {
    if (l1 == NULL && l2 == NULL) {
        return NULL;
    }
    struct ListNode *dummy = newNode(-1);
    struct ListNode *curr = dummy;
    int carry = 0;
    while ((l1 != NULL) || (l2 != NULL) || (carry > 0)) {
        int l1_val = (l1 != NULL) ? l1->val : 0;
        int l2_val = (l2 != NULL) ? l2->val : 0;
        int sum = carry + l1_val + l2_val;

        carry = (int) (sum / 10);
        curr->next = newNode(sum % 10);

        curr = curr->next;
        if (l1 != NULL) l1 = l1->next;
        if (l2 != NULL) l2 = l2->next;
    }
    curr = dummy->next;
    free(dummy);
    return curr;
}

源码分析

  1. 迭代能正常进行的条件为(l1 != NULL) || (l2 != NULL) || (carry > 0), 缺一不可。
  2. 对于空指针节点的处理可以用相对优雅的方式处理 - int l1_val = (l1 != NULL) ? l1->val : 0;
  3. 生成新节点时需要先判断迭代终止条件(l1 == NULL) && (l2 == NULL) && (carry <= 0), 避免多生成一位数0。 使用 dummy 节点可避免这一情况。

复杂度分析

没啥好分析的,时间和空间复杂度均为\(O(max(L1, L2))\)

Tags