全栈大前端

# 特性

链表的插入/删除效率较高，而访问效率较低;链表则不一定连续，因此其查找只能依靠别的方式，一般我们是通过一个叫 next 指针来遍历查找。链表其实就是一个结构体

  • 高效的增删操作 O(1)

  • 麻烦的访问操作 O(n)

# 高频题

# 链表有环（简单) (opens new window)

  • 解法一 (暴力法 map)

  • 解法二 (标记法)

const hasCycle = function (head){
     while (head){
        if(head.flag) return true
        head.flag=true
        head=head.next
     }
     return false
}
//时间复杂度：O(n)
//空间复杂度：O(n)
1
2
3
4
5
6
7
8
9
10
11
  • 解法三（快慢指针）
const hasCycle= function(head){
    //边界判断
    if(!head|| !head.next){
        return false
    }
    //快指针
    let fast =head.next.next
    //慢指针
    let slow =head.next
    while (fast!==slow){
        if(!fast || !fast.next) return false
        fast =fast.next.next
        slow =slow.next
    }
    return true 
}
//时间复杂度：O(n)
//空间复杂度：O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
  • 解法四（JSON.stringify()）
//利用 JSON.stringify() 不能序列化含有循环引用的结构
const hasCycle= function (head){
  try{
      JSON.stringify(head)
      return false
  }
  catch(err){
      return true
  }
}

//时间复杂度：O(n)
//空间复杂度：O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 链表中环的入口节点

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null

  • flag标记法
const detectCycle = function(head) {
    while(head){
        if(head.flag){
            return head;
        }else{
            head.flag = true;
            head = head.next;
        }
    }
    return null;
};
1
2
3
4
5
6
7
8
9
10
11
12
  • 快慢指针

声明两个指针 P1 P2

  1. 判断链表是否有环： P1 P2 从头部出发，P1走两步，P2走一步，如果可以相遇，则环存在

  2. 从环内某个节点开始计数，再回到此节点时得到链表环的长度 length

  3. P1、P2 回到head节点，让 P1 先走 length 步,当P2和P1相遇时即为链表环的起点

function EntryNodeOfLoop(pHead){
    if(!pHead||!pHead.next){
        return null;
    }
    let P1 =pHead.next;
    let P2 =pHead.next.next;
    // 1.判断是否有环
    while(P1 !=P2){
        if(P2===null || P2.next ===null){
            return null
        }
        P1 =P1.next;
        P2 =P2.next.next;
    }
    // 2.获取环的长度
    let temp =P1;
    let length =1;
    P1= P1.next;
    while (temp !=P1){
        P1=P1.next;
        length++
    }
    // 3.找公共节点
    P1=P2=pHead;
    while(length-- >0){
        P2=P2.next
    }
    while (P1 !=P2){
        P1=P1.next;
        P2=P2.next;
    }
    return P1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

# 反转链表(简单) (opens new window)

  • 迭代法

时间复杂度: O(n)

空间复杂度: O(1)

const reverseList=function(head){
    //初始化前驱节点为null
    let pre =null;
    //初始化目标节点为头节点
    let cur =head;
    //只要目标节点不为nul,遍历就得继续
    while(cur !==null){
        //记录一下 next 节点
        let next = cur.next;
        //反转指针
        cur.next=pre;
        //pre 往前走一步
        pre=cur
        // cur 往前走一步
        cur =next
    }
    //反转结束后,pre 就会变成链表头节点
    return pre
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
  • 递归

时间复杂度: O(n)

空间复杂度: O(n)

const reverseList= function(head){
 if(!head|| !head.next) return head
 //记录当前节点的下一个节点
 let next =head.next;
 let reverseHead =reverseList(next);
 //操作指针进行反转
 head.next =null;
 next.next =head;
 return reverseHead
}
1
2
3
4
5
6
7
8
9
10
11

# 合并两个有序链表（简单）

  • 思路
  1. 使用递归来解题
  2. 将两个链表头部较小的一个与剩下的元素合并
  3. 当两条链表中的一条为空时终止递归
//时间复杂度：O(m+n)
//空间复杂度：O(m+n)

const mergeTwoList =function (l1,l2){
    if(l1===null){
        return l2
    }
    if(l2===null){
        return l1
    }
    if(l1.val<l2.val){
        l1.next=mergeTwoList(l1.next,l2)
        return l1
    }else{
        l2.next=mergeTowList(l1,l2.next)
        return l2
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 从尾到头打印链表(简单) (opens new window)

  • 方法一 递归
  1. ‘递'阶段先走至链表末尾
  2. head===null 为递归终止条件
  3. '归'阶段依次将每个节点上到值加入列表，即可实现链表值的倒序输出
const reversePrint =function (head){
    return head===null?[]reversePrint(head.next).concat(head.val)
}

//时间复杂度: O(n)
//空间复杂度: O(n)
1
2
3
4
5
6
  • 方法二 栈
  1. 借助两个栈，先将链表中的每个节点的值push 进stack1
  2. 然后再从stack1 中pop 出每个节点的值放入stack2
const reversePrint =function (head){
     const stack1=[]
     const stack2=[]
     while(head){
         stack1.push(head.val)
         head=head.next
     }
     const k= stack1.length;
     for(let 0; i<k;i++){
         stack2[i]=stack1.pop()
     }
     return stack2
}

//时间复杂度: O(n)
//空间复杂度: O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 删除链表的倒数第N个节点(中等) (opens new window)

  • 快慢指针

先明确，删除倒数第 n 个结点，我们需要找到倒数第 n+1 个结点，删除其后继结点即可。

  1. 添加 prev 哨兵结点，处理边界问题。
  2. 借助快慢指针，快指针先走 n+1 步，然后快慢指针同步往前走，直到 fast.next 为 null。
  3. 删除倒数第 n 个结点，返回 prev.next。
const removeNthFromEnd =function (head,n){
    let prev =new ListNode(0),fast = prev,slow = prev;
    prev.next=head;
    while(n--){
        fast =fast.next;
    }
    while(fast&&fast.next){
        fast =fast.next;
        slow =slow.next;
    }
    slow.next =slow.next.next;
    return prev.next;
}

//时间复杂度：O(n)
//空间复杂度：O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 删除链表的节点

  • 思路
  1. 定位节点： 遍历链表，直到 head.val == val 时跳出，即可定位目标节点。
  2. 修改引用： 设节点 cur 的前驱节点为 pre ，后继节点为 cur.next ；则执行 pre.next = cur.next ，即可实现删除 cur 节点。
  • 流程
  1. 特例处理： 当应删除头节点 head 时，直接返回 head.next 即可。
  2. 初始化： pre = head , cur = head.next。
  3. 定位节点： 当 cur 为空 或 cur 节点值等于 val 时跳出。

保存当前节点索引，即 pre = cur 。

遍历下一节点，即 cur = cur.next 。

  1. 删除节点： 若 cur 指向某节点，则执行 pre.next = cur.next ；若 cur 指向 null ，代表链表中不包含值为 val 的节点。

  2. 返回值： 返回链表头部节点 head 即可。

//时间复杂度 O(N):N 为链表长度，删除操作平均需循环 N/2N/2 次，最差 NN 次。 
//空间复杂度 O(1): cur, pre 占用常数大小额外空间。

const deleteNode=function(head,val){
    if(head.val==val){
        return head.next
    }
    let pre =head,cur=head.next
    while(cur!=null && cur.val !=val){
        pre=cur;
        cur=cur.next;
    }
    if(cur!=null) pre.next=cur.next
    return head
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 删除排序链表中的重复元素 (opens new window)

  1. 将 curr 指针指向链表头节点
  2. 遍历链表，注意边界条件
  3. 如果当前节点与它后面的节点值相等，则删除它后面与它重复的节点
  4. 不重复则继续遍历，最后返回头节点
const deleteDuplicates=function (head){
    let curr =head 
    while (curr!= null && curr.next !==null){
        if(curr.val ===curr.next.val){
            curr.next =curr.next.next
        }else{
            curr =curr.next
        }
    }
    return head
}
1
2
3
4
5
6
7
8
9
10
11
12

# 求链表的中间节点(简单) (opens new window)

  • 快慢指针
  1. 使用快慢不同的两个指针遍历，快指针一次走两步，慢指针一次走一步
  2. 当快指针到达终点时，慢指针刚好走到中间

//时间复杂度：O(N) N 是给定链表的结点数目
//空间复杂度：O(1) 只需要常数空间存放 slow 和 fast 两个指针
const middleNode=function(head){
    let fast = head;
    let slow = head;
    while(fast&&fast.next){
        slow =slow.next;
        fast=fast.next.next
    }
    return slow
}
1
2
3
4
5
6
7
8
9
10
11
12
13

# 返回倒数第k个节点(简单) (opens new window)

  • 快慢指针
  1. 在头节点分别定义快、慢两个指针，在定义 n 计数器
  2. 快指针先行，直到与慢指针相差 k 时，慢指针也开始走
  3. 这样的话，当快指针遍历完成时，慢指针就刚好在倒数第 k 个值的位置了
const kthToLast =function (head,k){
    let fast =head;
    let slow =head;
    let n= 0;
    while (fast){
        fast = fast.next
        if(n>=k){
            slow= slow.next
        }
        n++
    }
    return slow.val
}

//时间复杂度 O(n)
//空间复杂度 O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 参考链接

面试链表不再怕 (opens new window) 几乎刷完了力扣所有的链表题，我发现了这些东西 (opens new window)

← 树 →