实战题目

以下题目都是来自LeetCode，可自行先去实践一下。

:::info 在面试中，链表的题目思维过程是比较简单的，一般对代码的简洁程度及实现能力比较高。 :::

题一：反转链表

题目地址：https://leetcode-cn.com/problems/reverse-linked-list/，题号：206。

【实现思路】

var reverseList = function(head) {
    let prev=head, curr=null;
    while(prev) {
        const temp = prev.next;
        prev.next = curr;
        curr = prev;
        prev = temp;
    }
    return curr;
};

题二：链表交换相邻元素

题目地址：https://leetcode-cn.com/problems/swap-nodes-in-pairs/，题号：24。

【实现思路】
这道题思路跟反转链表很像，定义一个临时的节点dummyHead，三个指针temp，node1，node2，交换node1和node2的指向。

var swapPairs = function(head) {
    if(!head || !head.next) { return head; }
    let dummyHead = {},temp=dummyHead;
    dummyHead.next = head;
    while(temp.next && temp.next.next) {
        let node1 = temp.next;
        let node2 = temp.next.next;
        temp.next = node2;
        node1.next = node2.next;
        node2.next = node1;
        temp = node1;
    }
    return dummyHead.next;
};

题三：判断链表是否有环

题目地址：https://leetcode-cn.com/problems/linked-list-cycle/，题号：141。题目太长，不做展示。

大致思路有三个：

• 硬做，对于数据量少的情况，通过设置一个时间，比如0.5s左右，然后一直查找next，看是否会走到null，这是一个解题思路，但不推荐，性能不好。

• set表。通过遍历整个链表，把已经遍历过的节点都存储在这个set表中，每次保存都先判断这个节点是否存在于这个set表，如果存在就代表有环，否则就代表没有。

  var hasCycle = function(head) {
    var set = new Set();
    while(head) {
        set.add(head);
        let next = head.next;
        if(next && set.has(next)) {
            return true;
        }
        head = next;
    }
    return false;
  };

• 第三种方法是快慢指针。快慢指针的方式类似于龟兔赛跑，快指针每次走2步，慢指针每次走1步，如果有环，那么最终这两个指针一定会相遇，否则快指针会先到达终点。

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

to be continue…