单向链表是什么？

1. 单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。
2. 链表中的数据是以节点来表示的，每个节点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个节点的地 址数据。如以下结构：    

             let nodeList1={

                             value:1,

                             next:{  value:2,

                                         next:{ value:3,next:null}

                                      }

                              }

　　

 

以“结点的序列”表示线性表称作线性链表（单链表）

.单链表是链式存取的结构，为找第 i 个数据元素，必须先找到第 i-1 个数据元素。

 

 

题目：两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。如下图：

 

 

 

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

 解析：

1.首先我们要将数组转为链表模式 例如：

function array2list(arr) {
    if (arr.length === 0) return null

    // 第一个节点
    let head = { value: arr[0], next: null },
        // 临时变量，在循环中存储上一个节点
        p = head,
        // 存储当前节点
        node = {}
    for (let i = 1; i < arr.length; i++) {
        // 构建当前节点
        node = {
            value: arr[i],
            next: null
        }
        
        // 将当前节点与之前节点连接
        p.next = node

        // p 是临时变量，之前和 head 共同指向同一个内存地址
        // 这里 p 被重新赋值了，和 node 共同指向同一个内存地址
        // 设置当前节点为之前节点
        p = node
    }
//注意：虽然没有对head进行操作，但由于数组与对象的数据有共享关系，所以p值改变head即改变
    return head
}
      

2.将两个数组用 arrayList2 ()生成后

var addTwoNumbers = function (l1, l2) {
    let head = null, tail = null;
    let carry = 0;
    while (l1 || l2) {
        const n1 = l1 ? l1.val : 0;
        const n2 = l2 ? l2.val : 0;
        const sum = n1 + n2 + carry;
        if (!head) {
            head = tail = new array2list(sum % 10);
        } else {
            tail.next = new array2list(sum % 10);
            tail = tail.next;
        }
        carry = Math.floor(sum / 10);
        if (l1) {
            l1 = l1.next;
        }
        if (l2) {
            l2 = l2.next;
        }
    }
    if (carry > 0) {
        tail.next = new array2list(carry);
    }
    return head;
};      
     

3.运行：

let arr1=[1,2,3],arr2=[1,3,4];
arr1=arrayList2(arr1);
arr2=arrayLis2t(arr2);
addTwoNumbers(arr1,arr2);//[7,5,2]