如果你还在为写链表相关的算法题而苦恼, 那一定是你写的太少了, 让我们从最简单的开始来进行闯关吧

1. 反转链表

反转链表是最简单常见并且经典的题, 是链表入门的必刷题, 如果你真的对链表了如指掌, 那么你是否可以在几分钟内写下好几种解题方法呢? 如果你是大佬, 请跳过, 如果你是小菜, 请思考~


这里给大家分享两个场景的解题思路 :

1.1. 迭代 :

迭代的核心就是从第一个节点开始, 让 两两链表的指向反转
思考一 ： 如何实现链表反转？
  这种情况下我们可以设想一下， 如果没有变量进行存储， 使用当前节点cur直接操作让下一个节点指向当前节点， 那么我们就会丢失cur的下一个节点，链表进行深深切断了， 所以我们必须使用一个变量next ，用来存储下一个节点
思考二： 结果应该如何返回呢？
   题目要求我们最终返回一个被反转的链表，以上面的实例为例， 我们是要返回节点5当做头节点的，但是在我们遍历的时候不知道链表的长度，等我们循环结束跳出的时候，cur和next都变成了null, 也就是5的下一个null节点, 所以我们需要一个pre节点来存储我们当前节点的上一个节点， 最终返回它
如图：

// 迭代
var reverseList= function(head) {
    let pre = null,next,cur = head;
    while(cur!=null){
        next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
};

1.2. 递归 :

递归的核心就是从最后一个节点开始，让 两两链表的指向反转
思考一： 递归的终止条件是什么
   因为链表的递归节点一般都是.next进行参数传入, 所以当当前节点的下一个节点不为空时（判断当前节点的下一个节点， 实现要判断当前节点是否为空， 否者代码会报错），我们再进行反转
思考二： 如何进行单向链表反转
  1.递归到最后可进行操作的节点一定是节点5， 节点5的下一个节点是null, 返回
  2.节点为2时， 将下一个节点指向当前节点， 也就是node.next.next=node;并且为了避免双向链表， 我们需要对当前节点的下一个节点置null

//递归
var reverseList = function(head) {
    if(head === null || head.next === null){
        return head;
    }
    const newHead = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
};

2.环形链表：

环形链表和普通链表的区别？
 环形链表和普通链表的区别, 环形链表进行遍历的时候会走之前走过的节点， 而普通链表一直遍历会到null

2.1. 哈希表

想到走过的节点就一定会想到比较，将走过的节点进行存储到哈希表中，如果当前节点在哈希表中已经存在，就返回true, 否则就存储到哈希表中
思考1： 如何使用哈希表
  首先我们需要创建哈希表，在JavaScript中， 使用new Set()方法可以直接进行创建， 里面可以存储任何类型的值，然后使用.add()方法将我们遍历到的链表存储到里面

// 哈希表法
var hasCycle = function(head) {
    if(head === null) return false;
    let fast=head,slow=head;
    let res = false;
    while(fast!=null&&fast.next!=null){
        fast = fast.next.next;
        slow = slow.next;
        if(fast === slow){
            res = true;
            break;
        }
    }
    return res;
};

2.2. 快慢指针

这个方法也称为龟兔赛跑算法，就是通过一个快指针， 和一个慢指针进行遍历， 在遍历过程中如果当快指针和慢指针指向的链表一样，就说明是环形链表， 否则就是普通链表
思考1： 快指针和慢指针是什么
  快指针就是一个指针走的快， 慢指针就是一个指针走的慢，这里我们一般默认慢指针一次走一个链表，而快指针一次走两个链表

// 快慢指针
var hasCycle = function(head) {
    if(head === null) return false;
    let fast=head,slow=head;
    let res = false;
    while(fast!=null&&fast.next!=null){
        fast = fast.next.next;
        slow = slow.next;
        if(fast === slow){
            res = true;
            break;
        }
    }
    return res;
};