NC40两个链表生成相加链表(没有额外空间复杂度的解法)

- 1、题目描述：

- 2、题目链接：

https://www.nowcoder.com/practice/c56f6c70fb3f4849bc56e33ff2a50b6b?tpId=188&tqId=37538&rp=1&ru=%2Factivity%2Foj&qru=%2Fta%2Fjob-code-high-week%2Fquestion-ranking&tab=answerKey
-3、 设计思想：

详细操作流程看下图：

-4、视频讲解链接B站视频讲解

-5、代码：
c++版本:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
     //链表的翻转
     ListNode* ReverseList(ListNode* pHead) {
        ListNode *res = NULL;
        ListNode *cur = pHead;
        while(cur != NULL){
            ListNode *temp = cur->next;
            cur->next = res;
            res = cur;
            cur = temp;
        }
        return res;
    }
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        ListNode* l1 = ReverseList(head1);//翻转链表l1
        ListNode* l2 = ReverseList(head2);//翻转链表l2
        ListNode* res = NULL;// 用于返回的链表
        int cnt = 0;//如果两个值的加和>10，就会产生进位，这个用来存储进位
        while(l1 || l2){
            int x1 = l1==nullptr? 0 : l1->val;
            int x2 = l2==nullptr? 0 : l2->val;
            int sum = x1 + x2 + cnt;//当前这一位的总和
            cnt = sum / 10;//查看当前加和是否有进位
            ///进行当前节点的插入
            ListNode *tempNode = new ListNode(sum % 10);
            tempNode->next = res;
            res = tempNode;
            l1 = l1==nullptr? nullptr: l1->next;
            l2 = l2==nullptr? nullptr: l2->next;
        }
        ///如果cnt>0那么就说明存在进位还得插入一个节点
        if(cnt > 0){
            ListNode *tempNode = new ListNode(cnt);
            tempNode->next = res;
            res = tempNode;
        }
        return res;

    }
};

Java版本：

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
     //翻转链表
    public static ListNode ReverseList(ListNode pHead) {
        ListNode res = null;
        ListNode cur = pHead;
        while(cur != null){
            ListNode temp = cur.next;
            cur.next = res;
            res = cur;
            cur = temp;
        }
        return res;
    }
    public ListNode addInList (ListNode head1, ListNode head2) {
        ListNode l1 = ReverseList(head1);//翻转链表l1
        ListNode l2 = ReverseList(head2);//翻转链表l2
        ListNode res = null;// 用于返回的链表
        int cnt = 0;//如果两个值的加和>10，就会产生进位，这个用来存储进位
        while(l1 != null || l2 != null){
            int x1 = l1==null? 0 : l1.val;
            int x2 = l2==null? 0 : l2.val;
            int sum = x1 + x2 + cnt;//当前这一位的总和
            cnt = sum / 10;//查看当前加和是否有进位
            ///进行当前节点的插入
            ListNode tempNode = new ListNode(sum % 10);
            tempNode.next = res;
            res = tempNode;
            l1 = l1==null? null: l1.next;
            l2 = l2==null? null: l2.next;
        }
        ///如果cnt>0那么就说明存在进位还得插入一个节点
        if(cnt > 0){
            ListNode tempNode = new ListNode(cnt);
            tempNode.next = res;
            res = tempNode;
        }
        return res;

    }
}

Python版本:

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

#
# 
# @param head1 ListNode类 
# @param head2 ListNode类 
# @return ListNode类
#
class Solution:
    #链表的翻转
    def ReverseList(self,pHead):
        res = None
        cur = pHead
        while cur:
            temp = cur.next
            cur.next = res
            res = cur
            cur = temp
        return res
    def addInList(self , head1 , head2 ):
        # write code here
        l1 = self.ReverseList(head1)#翻转链表l1
        l2 = self.ReverseList(head2)#翻转链表l2
        res = None #用于返回的链表
        cnt = 0#如果两个值的加和>10，就会产生进位，这个用来存储进位
        while l1 or l2:
            x1 = 0 if not l1 else l1.val
            x2 = 0 if not l2 else l2.val
            sum = x1 + x2 + cnt#当前这一位的总和
            cnt = sum // 10#查看当前加和是否有进位
            #进行当前节点的插入
            tempNode = ListNode(sum % 10)
            tempNode.next = res
            res = tempNode
            #链表的移动
            l1 = None if not l1 else l1.next
            l2 = None if not l2 else l2.next
        #最后一位的时候还得判断当时是否有进位如果存在进位就得在插入一个元素
        if cnt:
            tempNode = ListNode(cnt)
            tempNode.next = res
            res = tempNode
        return res

JavaScript版本：

/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */

/**
 * 
 * @param head1 ListNode类 
 * @param head2 ListNode类 
 * @return ListNode类
 */
 ///翻转链表
function ReverseList(pHead)
{
    // write code here
    let res = null;
    let cur = pHead;
    while(cur){
        let temp = cur.next;
        cur.next = res;
        res = cur;
        cur = temp;
    }
    return res;
}
function addInList( head1 ,  head2 ) {
    // write code here
    let l1 = ReverseList(head1);//翻转链表l1
    let l2 = ReverseList(head2);//翻转链表l2
    let res = null;//用于返回最终结果
    let cnt = 0;
    while(l1 || l2){
        let x1 = l1==null? 0 : l1.val;
        let x2 = l2==null? 0 : l2.val;
        let sum = x1 + x2 + cnt;//当前这一位的总和
        cnt = Math.floor(sum / 10);//查看当前加和是否有进位
        ///进行当前节点的插入
        let tempNode = new ListNode(sum % 10);
        tempNode.next = res;
        res = tempNode;
        //链表的移动
        l1 = l1==null? null: l1.next;
        l2 = l2==null? null: l2.next;
      }
    ///如果cnt>0那么就说明存在进位还得插入一个节点
    if(cnt){
        let  tempNode = new ListNode(cnt);
        tempNode.next = res;
        res = tempNode;
    }
    return res;
}
module.exports = {
    addInList : addInList
};