算法疑难(js实现)---6、反转链表

一、总结

一句话总结：

1、遍历链表，把链表里面的每个节点的值都拿下来，存在数组里面

2、再次遍历链表，将数组里面的值倒序的赋值给每一个节点的val域就实现了链表的反转

//反转链表
function reverseList(head){
    //1、遍历链表，把链表里面的每个节点的值都拿下来，存在数组里面
    //（在这里我们存的节点的值，而不是存的整个节点，这样是可以节约内存的）
    let arr=[];//arr用于存储链表的节点的值
    let p=head;//p用于遍历链表
    while(p){
        arr.push(p.val);
        p=p.next;
    }

    //2、再次遍历链表，将数组里面的值倒序的赋值给每一个节点的val域就实现了链表的反转
    //（我们没有考虑新建一个链表，而是用了原来的链表，可以节约创建新链表的时间和内存）
    p=head;
    while(p){
        p.val=arr.pop();
        p=p.next;
    }
    return head;
}

1、反转链表的注意点？

a、第一次遍历我们存的是节点的值而不是节点，这样可以节约内存

b、第二次遍历我们没有新建链表而是用的原链表，因为这样可以节约创建新链表的时间和内存

//反转链表
function reverseList(head){
    //1、遍历链表，把链表里面的每个节点的值都拿下来，存在数组里面
    //（在这里我们存的节点的值，而不是存的整个节点，这样是可以节约内存的）
    let arr=[];//arr用于存储链表的节点的值
    let p=head;//p用于遍历链表
    while(p){
        arr.push(p.val);
        p=p.next;
    }

    //2、再次遍历链表，将数组里面的值倒序的赋值给每一个节点的val域就实现了链表的反转
    //（我们没有考虑新建一个链表，而是用了原来的链表，可以节约创建新链表的时间和内存）
    p=head;
    while(p){
        p.val=arr.pop();
        p=p.next;
    }
    return head;
}

二、反转链表

博客对应课程的视频位置：6、反转链表
https://www.fanrenyi.com/video/20/242

 1 <!DOCTYPE html>
 2 <html lang="en">
 3 <head>
 4     <meta charset="UTF-8">
 5     <title>反转链表</title>
 6 </head>
 7 <body>
 8 <!--
 9 需求：
10 写一个函数，输入一个链表，反转链表后，输出新链表的表头。
11 
12 -->
13 <script>
14     //创建链表的节点：在js里面可以用构造函数来创建链表的节点
15     function Node(val){
16         this.val=val;
17         this.next=null;
18     }
19     //新建一个链表
20     function createList(arr){
21         let head=new Node(arr[0]);
22         let tail=head;
23         for(let i=1;i<=arr.length-1;i++){
24             tail.next=new Node(arr[i]);
25             tail=tail.next;
26         }
27         return head;
28     }
29     let list=createList([1,2,3,4,5]);
30     //console.log(list);
31 
32     //反转链表
33     function reverseList(head){
34         //1、遍历链表，把链表里面的每个节点的值都拿下来，存在数组里面
35         //（在这里我们存的节点的值，而不是存的整个节点，这样是可以节约内存的）
36         let arr=[];//arr用于存储链表的节点的值
37         let p=head;//p用于遍历链表
38         while(p){
39             arr.push(p.val);
40             p=p.next;
41         }
42 
43         //2、再次遍历链表，将数组里面的值倒序的赋值给每一个节点的val域就实现了链表的反转
44         //（我们没有考虑新建一个链表，而是用了原来的链表，可以节约创建新链表的时间和内存）
45         p=head;
46         while(p){
47             p.val=arr.pop();
48             p=p.next;
49         }
50         return head;
51     }
52 
53     console.log(reverseList(list));
54 
55 
56 </script>
57 </body>
58 </html>