• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

# JS刷题_链表专题

4周前 (05-13) 8次浏览

## 1 从尾到头打印链表

``````输入：head = [1,3,2]

``````
``````/**
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/
/**
* @return {number[]}
*/
const ans = [];
}
return ans;

};
``````

## 2 反转链表

``````输入: 1->2->3->4->5->NULL

``````

``````/**
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/
/**
* @return {ListNode}
*/
while(b){
let c = b.next;
b.next = a;  //很关键， 不要写反了 ， 是修改b.next
//
a = b;
b = c
}

return a;
};
``````

## 3 复杂链表的复制

``````/**
* Definition for singly-linked list with a random pointer.
* function ListNode(val) {
*     this.val = val;
*     this.next = this.random = null;
* }
*/

/**
* @return {ListNode}
*/
let map = new Map();
map.set(null, null); //很关键。js中如果是null，get是 undefined
//复制节点
while(node){
map.set(node,new ListNode(node.val));
node = node.next;
}

//复制节点的next 和 random
while(node){
map.get(node).next = map.get(node.next);  //此时如果node.next 为null，就不需要特判了，set中加好了
map.get(node).random = map.get(node.random);
node = node.next;
}

};
``````

## 4 剑指 Offer 25. 合并两个排序的链表

``````/**
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var merge = function(l1, l2) {
if(!l1) return l2;
if(!l2) return l1;

//合并两个有序链表，遍历一遍即可
let dummy = new ListNode(-1);
let cur = dummy;
while(l1 && l2){
if(l1.val < l2.val){
cur.next = new ListNode(l1.val);
l1 = l1.next;
cur = cur.next;
}else{
cur.next = new ListNode(l2.val);
l2 = l2.next;
cur = cur.next;
}
}
//尾巴
if(l1) cur.next = l1;
if(l2) cur.next = l2;
return dummy.next;

};
``````

## 5 剑指 Offer 22. 链表中倒数第k个节点

``````/**
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/
/**
* @param {number} k
* @return {ListNode}
*/
var getKthFromEnd = function(head, k) {
let n = 0;
while(cur){
n++;
cur = cur.next;
}

//倒数第k个节点？ 倒数第1个节点 从第一个走n-1步
//倒数第2个    n-2
if(k > n) return null;
for(let i = 0; i < n - k; i ++){
cur = cur.next;
}
return cur;

};
``````

## 6 142. 环形链表 II

``````/**
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/

/**
* @return {ListNode}
*/
//1. 判断是否有环
while(p1 != p2){
if(p2 === null || p2.next === null) return null;
p1 = p1.next;
p2 = p2.next.next;
}

//2.相遇 获取环的长度
let length = 1;
let tmp = p1;
p1 = p1.next;
while(tmp != p1){
p1 = p1.next;
length++;
}

//3.找到公共节点
for(let i = 0; i < length ; i++){
p1 = p1.next;
}
while(p1 != p2){
p1 = p1.next;
p2 = p2.next;
}
return p1.val;

};
``````

## 剑指 Offer 52. 两个链表的第一个公共节点

``````/**
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/

/**
* @return {ListNode}
*/
while(p != q){
if(p) p = p.next;
if(q) q = q.next;
}
return p;
};
``````

## 剑指 Offer 62. 圆圈中最后剩下的数字

``````/**
* @param {number} n
* @param {number} m
* @return {number}
*/
var lastRemaining = function(n, m) {
if( n === 1) return 0;
else return (lastRemaining(n-1, m) + m) % n;
};
``````

## 剑指 Offer 18. 删除链表的节点

``````/**
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/
/**
* @param {number} val
* @return {ListNode}
*/
var deleteNode = function(head, val) {
let dummy = new ListNode(-1);
let node = dummy;
while(node.next){
if(node.next.val === val){
node.next = node.next.next;
break;
}
node = node.next;
}
return dummy.next;

};
``````

## 82. 删除排序链表中的重复元素 II

``````/**
* function ListNode(val, next) {
*     this.val = (val===undefined ? 0 : val)
*     this.next = (next===undefined ? null : next)
* }
*/
/**
* @return {ListNode}
*/
let dummy = new ListNode(-1);

let p = dummy;
while(p.next){
let q = p.next;
while(q && p.next.val === q.val){
q = q.next
}
//判断长度是否为1
if(p.next.next == q) p = p.next;
else p.next = q;
}
return dummy.next;
};
``````