链表链表高频整理

链表基本实现（熟练默写） https://www.yuque.com/wuzhao/myev2y/vug3f5

• 单链表
• 双向链表
• 跳表

算法题目（熟练默写）

• 回文链表 —- 拼接正反字符串
• 反转链表
• 快慢指针系列
  • 环形链表 —- 快慢指针套圈
  • 删除链表中倒数第n个元素 —- 快慢指针先走n步
  • 返回链表倒数第k个元素 —- 同删除倒数第k个元素 返回慢指针
  • 获取链表中间的元素 —- 快指针两倍速
  • 删除链表中间节点 —- 同获取中间节点
• 排序链表
• 相交链表
• 奇偶链表

数据结构在知名程序中的应用（了解）

• Redis为什么用跳表而不用平衡树？https://zhuanlan.zhihu.com/p/23370124
• LRU 算法的原理及实现 https://zhuanlan.zhihu.com/p/114399353

234. 回文链表

思路
1. 定义两个临时变量，存储正、反两个拼接的字符串
2. 遍历链表，进行字符串拼接
3. 比较正、反字符串是否相同

var isPalindrome = function(head) {
    let str_1 = ''  
    let str_2 = ''
    while(head){
        const v = head.val
        str_1 = str_1 + v // 在前边补上
        str_2 = v + str_2 // 在后边补上
        head = head.next
    }
    return str_1 === str_2
};

复杂度分析

• 时间复杂度：过程中只会遍历一遍链表，因此，时间复杂度为
• 空间复杂度：过程中产生 2 个临时变量存储，因此，空间复杂度为

206. 反转链表

思路

1. 先记住下一个节点
2. 当前节点next指向前一个
3. “前一个”指针指向当前
4. 通过temp移动当前指针到下一个

   var reverseList = function(head) {
    let pre = null,cur = head,temp = null
    while(cur !== null){
        temp = cur.next;//修改前先记住下一个节点
        cur.next = pre; //修改当前指向指向前一个（第一个节点pre是null）
        pre = cur; //记录前一个节点，供下次循环使用
        cur = temp; // cur通过temp找到下一个要找的节点点
    }
    return pre //cur会多循环到null
   };
   

   复杂度分析

• 时间复杂度：

上述解法中，遍历了一次链表，这将耗费 的时间。

• 空间复杂度：

上述解法中，申请了两个额外的临时存储空间，这将耗费 的空间。

双指针模板系列

141. 环形链表

思路
两个运动员，快的会套圈

var hasCycle = function(head) {
    if(!head || !head.next) return false
    let fast = head.next
    let slow = head
    while(slow!==fast){
        if(!fast || !fast.next){ // 快指针跑完了没遇到慢支针
            return false
        }
        fast = fast.next.next
        slow = slow.next
    }
    return true

};

复杂度分析

• 时间复杂度：过程中只会遍历一遍链表，因此，时间复杂度为
• 空间复杂度：开辟了两个变量

19. 删除链表的倒数第N个节点

思路
快指针先走N步骤慢指针再走

var removeNthFromEnd = function(head, n) {
    let slow = fast = head
    for(let i = 0;i < n;i++){
        fast = fast.next
    }
    if(!fast){  //要删除第一个节点
        return head.next
    }
    while(fast.next !== null){
        slow = slow.next
        fast = fast.next
    }
    slow.next = slow.next.next
    return head

};

复杂度分析

• 时间复杂度： 该算法对含有 n个结点的列表进行了单层遍历，因此，时间复杂度为
• 空间复杂度： 该算法只用了常量级的额外空间。故空间复杂度为

剑指Offer 22. 链表中倒数第k个元素

思路 （同删除倒数第N个节点）
快指针先走N步骤慢指针再走，返回慢指针当head

var getKthFromEnd = function(head, k) {
    let fast = head
    let slow = head
    for(let i = 0; i < k; i++){
        fast = fast.next
    }
    while(fast !== null){
        slow = slow.next
        fast = fast.next
    }
    return slow
};