1 从尾到头打印链表
剑指offer_06题
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
输入：head = [1,3,2]
输出：[2,3,1]
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {number[]}
*/
var reversePrint = function(head) {
const ans = [];
while(head){
ans.unshift(head.val);
head = head.next;
}
return ans;
};
2 反转链表
剑指offer_24题
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
思路：每次都需要一个中间节点，进行反转
获取 head，和head.next
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
if(!head || !head.next) return head;
let a = head;
let b = head.next;
while(b){
let c = b.next;
b.next = a; //很关键， 不要写反了 ， 是修改b.next
//
a = b;
b = c
}
head.next = null;
return a;
};
这个题目，写错过一次，很烦！！！
3 复杂链表的复制
剑指offer_35题
带有next 和 random指针的链表复制，核心：哈希表
/**
* Definition for singly-linked list with a random pointer.
* function ListNode(val) {
* this.val = val;
* this.next = this.random = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var copyRandomList = function(head) {
if(!head) return null;
let map = new Map();
map.set(null, null); //很关键。js中如果是null，get是 undefined
let node = head;
//复制节点
while(node){
map.set(node,new ListNode(node.val));
node = node.next;
}
//复制节点的next 和 random
node = head;
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;
}
return map.get(head);
};
4 剑指 Offer 25. 合并两个排序的链表
思路，遍历一遍
/**
* Definition for singly-linked list.
* 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个节点
思路：注意倒数第k个的含义： 倒数第1个就是 走 n-1步
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
var getKthFromEnd = function(head, k) {
let n = 0;
let cur = head;
while(cur){
n++;
cur = cur.next;
}
//倒数第k个节点？ 倒数第1个节点 从第一个走n-1步
//倒数第2个 n-2
cur = head;
if(k > n) return null;
for(let i = 0; i < n - k; i ++){
cur = cur.next;
}
return cur;
};
6 142. 环形链表 II
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var entryNodeOfLoop= function(head) {
if(!head || !head.next) return null;
let p1 = head.next;
let p2 = head.next.next;
//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.找到公共节点
p1 = p2 = head;
for(let i = 0; i < length ; i++){
p1 = p1.next;
}
while(p1 != p2){
p1 = p1.next;
p2 = p2.next;
}
return p1.val;
};
剑指 Offer 52. 两个链表的第一个公共节点
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} headA
* @param {ListNode} headB
* @return {ListNode}
*/
var getIntersectionNode = function(headA, headB) {
let p = headA, q = headB;
while(p != q){
if(p) p = p.next;
else p = headB;
if(q) q = q.next;
else q = headA;
}
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. 删除链表的节点
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @param {number} val
* @return {ListNode}
*/
var deleteNode = function(head, val) {
let dummy = new ListNode(-1);
dummy.next = head;
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
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var deleteDuplicates = function(head) {
let dummy = new ListNode(-1);
dummy.next = head;
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;
};