链表相加二

• 先反转链表，再模拟加法运算，最后反转链表

题目描述

假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。 给定两个这种链表，请生成代表两个整数相加值的结果链表。

例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。

示例

输入：[9,3,7],[6,3]
返回值：{1,0,0,0}

C++实现

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here

        // 1. reverse link list
        // 2. add operation
        // 3. reverse
        ListNode *h1 = reverse(head1);
        ListNode *h2 = reverse(head2);

        ListNode *h = nullptr, *p = nullptr;
        pair<int, int> carry = {0, 0};
        for (ListNode *p1=h1, *p2=h2; p1 || p2 || carry.second > 0;) {
            int val1 = p1 ? p1->val : 0;
            int val2 = p2 ? p2->val : 0;
            if (p1) p1 = p1->next;
            if (p2) p2 = p2->next;

            int sum = val1 + val2 + carry.second;
            carry = {sum%10, sum/10};

            ListNode *q = new ListNode(carry.first);
            if (!h) {
                h = q;
                p = q;
            } else {
                p->next = q;
                p = q;
            }
        }

        ListNode *ret = reverse(h);
        return ret;
    }

private:
    ListNode* reverse(ListNode* head) {
        ListNode *prev = nullptr;
        ListNode *curr = head;
        while (curr) {
            ListNode *next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

golang实现

package main

import (
	//"fmt"
	. "nc_tools"

	//"golang.org/x/text/currency"
)

/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param head1 ListNode类
 * @param head2 ListNode类
 * @return ListNode类
 */
func addInList( head1 *ListNode ,  head2 *ListNode ) *ListNode {
    // write code here
    h1 := reverse(head1)
    h2 := reverse(head2)

    // add operator
    var h, p *ListNode
    carry := [2]int{0, 0}
    for p1,p2 := h1,h2; p1 != nil || p2 != nil || carry[1] > 0; {
        val1, val2 := 0, 0
        if p1 != nil {
            val1 = p1.Val
            p1 = p1.Next
        }
        if p2 != nil {
            val2 = p2.Val
            p2 = p2.Next
        }
        sum := val1 + val2 + carry[1]
        carry = [2]int{sum%10, sum/10}

        // create link list
        q := &ListNode{Val: carry[0]}
        if h == nil {
            h = q
            p = q
        } else {
            p.Next = q;
            p = q;
        }
    }

    ret := reverse(h)
    return ret
}

func reverse(head *ListNode) *ListNode {
    var prev *ListNode
    curr := head
    for curr != nil {
        next := curr.Next
        curr.Next = prev
        prev, curr = curr, next
    }
    return prev
}