门徒计划.md

门徒

彩蛋课程：xue.kaikeba.com/static/KKB000000.mp4

题库-链表

链表：线性的顺序存储数据结构，每一个节点里存到下一个节点的指针(Pointer)。

链表应用场景

• 系统内存分配
• LRU缓存

1. 链表是否有环

• 解题思路：

  • 哈希表存储节点，判断节点是否重复出现

  • 快慢指针，快速理解：两个不同速度的人跑圈，一定会再次相遇

    • var hasCycle = function(head) {
          if(head == null || head.next == null){
              return false
          }
          var slow = head.next
          var fast = head.next.next
          while(slow != fast && fast != null && fast.next != null ){
              slow = slow.next
              fast = fast.next.next
          }
          return fast != null && fast.next != null
      };

2. 环形链表的起点

• 解题思路：如果有环，则链表起点距环的起点距离，等于相遇点距离环的起点距离

  • var detectCycle = function(head) {
        if(head == null || head.next == null) {
            return null
        }
        var slot = head.next
        var fast = head.next.next
        while(slot != fast && fast != null && fast.next != null){
            slot = slot.next;
            fast = fast.next.next;
        }
        if(fast == null || fast.next == null){
            return null
        }
        // 此时slot 和 fast相遇，表示有环
        // 将慢指针移动到head，快慢指针同时往后走一步，直到再次相遇，相遇点就是环的起点
        slot = head
        while(slot != fast){
            slot = slot.next;
            fast = fast.next;
        }
        return slot;
    };

3. 快乐数


• 解题思路：要理解题目中的意思，平方和不是1，则会无限循环！ 据此可以在逻辑上转换成链表是否有环，且相遇点是否为1，相遇点是1则是快乐数，相遇数不是1，则不是快乐数

  • /**
     * @param {number} n
     * @return {boolean}
     */
    var isHappy = function(n) {
        var getNext = x=>{
            var z = 0;
            while(x){
                z += (x%10)*(x%10)
                x = Math.floor(x/10)
            }
            return z;
        }
    
        var slow = getNext(n);
        var fast = getNext(getNext(n))
        while(slow !== fast){
            slow = getNext(slow);
            fast = getNext(getNext(fast))
        }
        return fast===1;
    };

4. 链表反转