我是靠谱客的博主 幸福红酒，最近开发中收集的这篇文章主要介绍leetcode每天5题-Day251. 移除链表元素2. 设计链表3. 翻转链表4.两两交换链表中的节点5. 删除链表的倒数第 N 个结点6.链表相交7.环形链表 II，觉得挺不错的，现在分享给大家，希望可以做个参考。
概述
目录
- 1. 移除链表元素
- 2. 设计链表
- 3. 翻转链表
- 4.两两交换链表中的节点
- 5. 删除链表的倒数第 N 个结点
- 6.链表相交
- 7.环形链表 II
链表专项????
单链表
双链表
循环链表可以用来解决约瑟夫环问题
链表的定义：
1. 移除链表元素
203. 移除链表元素-简单
b站视频讲解-代码随想录
因为移除头节点与别的节点不同，所以根据移除头节点的操作方式分为以下两种方法
①原链表删除元素
var removeElements = function(head, val) {
while(head!==null&&head.val===val){
head=head.next;
}
let temp=head;
while(temp!==null&&temp.next!==null){
if(temp.next.val===val){
temp.next=temp.next.next;
}else{
temp=temp.next;
}
}
return head;
};
②使用虚拟头节点
设置一个虚拟头结点，这样原链表的所有节点就都可以按照统一的方式进行移除了
var removeElements = function(head, val) {
// 添加虚拟头节点
const dummy=new ListNode(0,head);
let temp=dummy;
while(temp.next!==null){
if(temp.next.val===val){
temp.next=temp.next.next;
}else{
temp=temp.next;
}
}
return dummy.next;
};
2. 设计链表
707. 设计链表-中等
b站视频讲解-代码随想录
class LinkNode {
constructor(val, next) {
this.val = val;
this.next = next;
}
}
/**
* Initialize your data structure here.
* 单链表 储存头尾节点 和 节点数量
*/
var MyLinkedList = function() {
this._size = 0;
this._tail = null;
this._head = null;
};
/**
* Get the value of the index-th node in the linked list. If the index is invalid, return -1.
* @param {number} index
* @return {number}
*/
MyLinkedList.prototype.getNode = function(index) {
if(index < 0 || index >= this._size) return null;
// 创建虚拟头节点
let cur = new LinkNode(0, this._head);
// 0 -> head
while(index-- >= 0) {
cur = cur.next;
}
return cur;
};
MyLinkedList.prototype.get = function(index) {
if(index < 0 || index >= this._size) return -1;
// 获取当前节点
return this.getNode(index).val;
};
/**
* Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
* @param {number} val
* @return {void}
*/
MyLinkedList.prototype.addAtHead = function(val) {
const node = new LinkNode(val, this._head);
this._head = node;
this._size++;
if(!this._tail) {
this._tail = node;
}
};
/**
* Append a node of value val to the last element of the linked list.
* @param {number} val
* @return {void}
*/
MyLinkedList.prototype.addAtTail = function(val) {
const node = new LinkNode(val, null);
this._size++;
if(this._tail) {
this._tail.next = node;
this._tail = node;
return;
}
this._tail = node;
this._head = node;
};
/**
* Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted.
* @param {number} index
* @param {number} val
* @return {void}
*/
MyLinkedList.prototype.addAtIndex = function(index, val) {
if(index > this._size) return;
if(index <= 0) {
this.addAtHead(val);
return;
}
if(index === this._size) {
this.addAtTail(val);
return;
}
// 获取目标节点的上一个的节点
const node = this.getNode(index - 1);
node.next = new LinkNode(val, node.next);
this._size++;
};
/**
* Delete the index-th node in the linked list, if the index is valid.
* @param {number} index
* @return {void}
*/
MyLinkedList.prototype.deleteAtIndex = function(index) {
if(index < 0 || index >= this._size) return;
if(index === 0) {
this._head = this._head.next;
// 如果删除的这个节点同时是尾节点，要处理尾节点
if(index === this._size - 1){
this._tail = this._head
}
this._size--;
return;
}
// 获取目标节点的上一个的节点
const node = this.getNode(index - 1);
node.next = node.next.next;
// 处理尾节点
if(index === this._size - 1) {
this._tail = node;
}
this._size--;
};
// MyLinkedList.prototype.out = function() {
// let cur = this._head;
// const res = [];
// while(cur) {
// res.push(cur.val);
// cur = cur.next;
// }
// };
/**
* Your MyLinkedList object will be instantiated and called as such:
* var obj = new MyLinkedList()
* var param_1 = obj.get(index)
* obj.addAtHead(val)
* obj.addAtTail(val)
* obj.addAtIndex(index,val)
* obj.deleteAtIndex(index)
*/
3. 翻转链表
206. 反转链表-简单
b站视频讲解-代码随想录
①双指针
var reverseList = function(head) {
// 初始化
let pre=null,cur=head;
let temp=null;
while(cur){
// 在改变cur指向之前用temp存cur要移动的下一个位置
temp=cur.next;
cur.next=pre;
pre=cur;
cur=temp;
}
return pre;
};
②递归
根据双指针的写法写递归
var reverse = function(cur,pre) {
if(cur === null) return pre;
let temp=cur.next;
cur.next=pre;
return reverse(temp,cur); // 相当于更新pre和cur的值 ---> 根据双指针解法中的pre=cur; cur=temp;
};
var reverseList = function(head) {
// 此处参数值就是给cur和pre初始化
return reverse(head,null);
};
从后向前翻转????
var reverse = function(head) {
if(!head || !head.next) return head;
// 从后往前翻
const pre = reverse(head.next);
head.next = pre.next;
pre.next = head;
return head;
}
var reverseList = function(head) {
let cur = head;
while(cur && cur.next) {
cur = cur.next;
}
reverse(head);
return cur;
};
4.两两交换链表中的节点
24. 两两交换链表中的节点-中等
b站视频讲解-代码随想录
迭代
var swapPairs = function(head) {
const dummy = new ListNode(0);
dummy.next = head;
let cur=dummy;
// 顺序不可颠倒 否则空指针异常
while(cur.next !== null && cur.next.next !== null){
let temp=cur.next;
// 因为要改变节点2的指向 所以先用temp1把节点3保存下来
let temp1=cur.next.next.next;
// 让cur指向节点2
cur.next=cur.next.next;
// 让节点2指向节点1
cur.next.next=temp;
// 让节点1指向节点3
temp.next=temp1;
// 让cur后移两位 交换下两个节点
cur=cur.next.next;
}
return dummy.next;
};
代码随想录版
var swapPairs = function (head) {
let ret = new ListNode(0, head), temp = ret;
while (temp.next && temp.next.next) {
let cur = temp.next.next, pre = temp.next;
pre.next = cur.next;
cur.next = pre;
temp.next = cur;
temp = pre;
}
return ret.next;
};
5. 删除链表的倒数第 N 个结点
19. 删除链表的倒数第 N 个结点-中等
b站视频讲解-代码随想录
①双指针
经典双指针题目，先让快指针走(n+1)步，然后快慢指针一起走，当快指针指向NULL时，慢指针指向的即为要删节点的前一个节点。
var removeNthFromEnd = function(head, n) {
if(!head || !head.next) return null;
// let slow=head,fast=head;
let dummyHead = new ListNode(0,head);
let slow=dummyHead,fast=dummyHead;
while(n--){
fast=fast.next;
}
while(fast.next){
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummyHead.next;
};
本来我写的是 return head 但运行结果不对 改成了return dummyHead.next 就对了 不明白 又没改动head 为什么return head 运行结果不对呢
6.链表相交
面试题 02.07. 链表相交-简单
首先取到两条链表的长度，然后让较长链表的指针移动两链表长度差值（len1-len2）个位置，两个指针再同时移动。
var getLen = function(head){
let len=0,cur=head;
while(cur){
len++;
cur=cur.next;
}
return len;
}
var getIntersectionNode = function(headA, headB) {
let curA = headA,curB = headB;
let len1 = getLen(headA);
let len2 = getLen(headB);
if(len2 > len1){
// 下面交换变量注意加 “分号” ，两个数组交换变量在同一个作用域下时
// 如果不加分号，下面两条代码等同于一条代码: [curA, curB] = [lenB, lenA]
[curA,curB] = [curB,curA];
[len1,len2] = [len2,len1];
}
let i = len1 - len2;
while(i--){
curA = curA.next;
}
while(curA && curA !== curB){
curA = curA.next;
curB = curB.next;
}
return curA;
};
7.环形链表 II
142. 环形链表 II-中等
b站视频讲解-代码随想录
快慢指针
快指针每次走两步，慢指针每次走一步，快指针一定先进环，当慢指针也进环后，就是快指针以每次移动一步的速度去靠近慢指针，两个指针一定会相遇。
var detectCycle = function(head) {
let slow = head,fast = head;
// 因为快指针每次走两步 所以还要判断 fast.next !== null
while(fast !== null && fast.next !== null){
fast = fast.next.next;
slow = slow.next;
// 当快慢指针相遇时
if(fast === slow){
// index为相遇点
let index = fast;
// index1为头节点
let index1 = head;
// index与index1同时移动 两指针的相遇点即为环的入口
while(index !== index1){
index = index.next;
index1 = index1.next;
}
return index;
}
}
return null;
};
看下图，很好理解????
来自????代码随想录-环形链表 II
最后
以上就是幸福红酒为你收集整理的leetcode每天5题-Day251. 移除链表元素2. 设计链表3. 翻转链表4.两两交换链表中的节点5. 删除链表的倒数第 N 个结点6.链表相交7.环形链表 II的全部内容，希望文章能够帮你解决leetcode每天5题-Day251. 移除链表元素2. 设计链表3. 翻转链表4.两两交换链表中的节点5. 删除链表的倒数第 N 个结点6.链表相交7.环形链表 II所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复