203.移除链表元素
题目描述：
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回新的头节点 。
示例 1：
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
示例 2：
输入：head = [], val = 1
输出：[]
示例 3：
输入：head = [7,7,7,7], val = 7
输出：[]
解题思路
- 如果头节点值等于目标值，需要删除头节点，head = head.next
- 如果存在中间节点值等于目标值，需要删除中间节点，cur.next = cue.next.next
方法一：直接在原链表进行移除操作
注意
1 判断头节点时要用while循环，因为可能存在多个相同节点的值与目标值相等，比如示例三；
var removeElements = function(head, val) {
// 删除头结点
while(head && head.val === val) {
head = head.next
}
let cur = head
// 删除中间节点
while(cur && cur.next) {
if (cur.next.val === val) {
cur.next = cur.next.next
} else {
cur = cur.next
}
}
return head;
};
- 时间复杂度：O(n)
- 空间复杂度：O(1)
方法二：利用虚拟头节点
什么是虚拟头节点
在链表头设置一个假的节点dummyHead，该节点存储的数据内容没有实际意义，其指向为真正的头节点。
目的
是由于一般的头节点没有对应的前序，所以需要特殊处理，加入虚拟头节点，可以统一处理逻辑。
如何设置虚拟头节点
// js中
const dummyHead = new ListNode(0, head)
注意
1 返回结果为虚拟头节点的next；
var removeElements = function(head, val) {
const dummyHead = new ListNode(0, head) // 设置虚拟头节点
let cur = dummyHead
while(cur && cur.next) {
if (cur.next.val === val) {
cur.next = cur.next.next
} else {
cur = cur.next
}
}
return dummyHead.next;
};
- 时间复杂度：O(n)
- 空间复杂度：O(1)
707.设计链表
由于题目比较长，这里请直接看上述链接~
主要实现以下五个方法：
- 获取链表第index个节点的数值
- 在链表的最前面插入一个节点
- 在链表的最后面插入一个节点
- 在链表第index个节点前面插入一个节点
- 删除链表的第index个节点
class LinkNode {
constructor(val, next) {
this.val = val;
this.next = next;
}
}
var MyLinkedList = function() {
this._size = 0;// 记录节点个数
this._head = null; // 存储头节点
this._tail = null; // 存储尾节点
};
// 定义方法：根据索引返回对应的节点信息
MyLinkedList.prototype.getNode = function(index) {
if (index < 0 || index >= this._size) {
return null;
}
// 定义虚拟节点
let cur = new LinkNode(0, this._head);
while(index >= 0) {
cur = cur.next;
index--;
}
return cur;
}
/**
* @param {number} index
* @return {number}
*/
MyLinkedList.prototype.get = function(index) {
if (index < 0 || index >= this._size) {
return -1;
}
return this.getNode(index).val;
};
/**
* @param {number} val
* @return {void}
*/
MyLinkedList.prototype.addAtHead = function(val) {
let node = new LinkNode(val, this._head);
// 更新头节点
this._head = node;
this._size++;
// 如果没有尾节点时，更新尾节点
if (!this._tail) {
this._tail = node;
}
};
/**
* @param {number} val
* @return {void}
*/
MyLinkedList.prototype.addAtTail = function(val) {
let node = new LinkNode(val, null);
this._size++;
// 如果不存在尾节点
if (!this._tail) {
this._head = node;
this._tail = node;
} else {
// 先更新当前尾节点的next
this._tail.next = node;
// 再更新尾节点为最新节点
this._tail = node;
}
};
/**
* @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;
}
let preNode = this.getNode(index - 1);
let nextNode = this.getNode(index);
let node = new LinkNode(val, null);
preNode.next = node;
node.next = nextNode;
this._size++;
};
/**
* @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--;
};
206.反转链表
题目描述：
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表 。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2]
输出：[2,1]
示例 3：
输入：head = []
输出：[]
解题思路
- 定义一个pre指针，初始化为null
- 临时变量接收cur.next，并将cur.next 赋值为pre即null，此时当前节点的next已经指向null了
- 重新赋值pre为最新的cur，即数值为头节点，指向为null
- 更新当前节点为下一个节点
var reverseList = function(head) {
let pre = null;
let temp;
let cur = head;
while(cur) {
temp = cur.next
cur.next = pre
pre = cur
cur = temp
}
return pre
};
- 时间复杂度：O(n)
- 空间复杂度：O(1)
网友评论