YSMull
<-- Algorithm

Add Two Numbers

原题目地址

题目描述

每一个链表代表一个数,比如 2->3->4->null 代表的就是 432。现在输入是两个链表,代表两个数,输出是这两个数的和对应的链表。

分析

这是我的第一篇算法记录,不能为了做题而做题,而应该多思考我们能够从一道题中获得什么东西。
这道题思路上比较简单,就是从链表的第一个结点开始,计算相加和进位。但是有一个编程技巧可以简化我们代码的表达。

int val1 = (p1 == NULL) ? 0 : p1->val;
int val2 = (p2 == NULL) ? 0 : p2->val;

当其中一个链走到头但另一个链没有走到头的时候,另一个链表的节点在下一次循环中,值为0。如果不采用这种方式,那么我们可能要分别判断如果p1到头了该怎么做,p2到头了改怎么做等等。

总结一下:

  1. 当有多个数据结构需要并行操作互运算时,为了防止体量的不同而导致逻辑处理变复杂,可考虑采用这种方式来清洁代码逻辑。
  2. 不带头结点的单链表建表套路。

代码

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode *p1 = l1;
    struct ListNode *p2 = l2;
    struct ListNode *head = NULL;
    struct ListNode *ptr = NULL;
    int carry = 0;
    while (p1 != NULL || p2 != NULL || carry) {
        int val1 = (p1 == NULL) ? 0 : p1->val;
        int val2 = (p2 == NULL) ? 0 : p2->val;
        int newVal = val1 + val2 + carry;

        carry = newVal / 10;
        newVal %= 10;

        if (head == NULL) {
            head = (struct ListNode *)malloc(sizeof(struct ListNode));
            head->val = newVal;
            head->next = NULL;
            ptr = head;
        } else {
            struct ListNode *newNode = (struct ListNode *)malloc(sizeof(struct ListNode));
            newNode->val = newVal;
            newNode->next = NULL;
            ptr->next = newNode;
            ptr = newNode;
        }
        if (p1 != NULL) {
            p1 = p1->next;
        }
        if (p2 != NULL) {
            p2 = p2->next;
        }
    }
    return head;
}