YSMull
<-- algorithm



原题链接

2021-04-21 rust重写

impl Solution {
    pub fn add_two_numbers(mut l1: Option<Box<ListNode>>, mut l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut sentry = ListNode::new(0);
        let mut cur = &mut sentry;
        let mut p = 0;
        while l1.is_some() || l2.is_some() || p > 0 {
            let v1 = if let Some(node) = &l1 { node.val } else { 0 };
            let v2 = if let Some(node) = &l2 { node.val } else { 0 };
            let s = (v1 + v2 + p) % 10;
            p = (v1 + v2 + p) / 10;
            cur.next = Some(Box::new(ListNode::new(s)));
            cur = cur.next.as_mut().unwrap();
            if let Some(n) = l1 { l1 = n.next; }
            if let Some(n) = l2 { l2 = n.next; }
        }
        return sentry.next;
    }
}

题目描述

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

分析

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

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

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

总结一下:

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

代码(2017-03-21)

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;
}