Я видел исходный код Vue в апреле и мае прошлого года. Если я правильно помню, класс Cache должен быть реализован со связанным списком.Хотя он мало используется, но также очень необходимо освоить его как важную часть структуры данных.Дальше в основном объясняется с односвязным списком .
Начинать
Для простоты написания и тестирования сначала настройте несколько стандартных классов.
// 链表节点
class ListNode{
constructor(val){
this.val = val;
this.next = null;
}
}
// 将数组转化为链表
class chainList(arr){
let head = new ListNode(arr[0]);
let tail = head;
for (let i = 1; i < arr.length; i++) {
let node = new ListNode(arr[i]);
tail.next = node;
tail = node;
}
return head;
}
// 构建一个栈
const createStack = () => {
class Stack{
constructor(){
this.top = 0;
this.stores = [];
}
push(item){
this.top++;
return this.stores.push(item)
}
pop(){
this.top--
return this.stores.pop()
}
peer(){
return this.stores[this.stores.length-1]
}
isEmpty(){
return this.top == 0;
}
}
return new Stack();
}
тема
Чтобы умело использовать связанный список, лучше задать больше вопросов
Перевернуть связанный список I
样例
给出一个链表1->2->3->null，这个翻转后的链表为3->2->1->null
挑战
在原地一次翻转完成
Используйте обратный порядок стека «первым пришел — последним вышел»
const reverse = function (head) {
if (!head){
return null;
}
let node = head;
let stack = createStack();
while (node != null) {
stack.push(node);
node = node.next;
}
let newHead = null, tail = null;
while (!stack.isEmpty()) {
let node = stack.pop();
if (!newHead) {
newHead = tail = node;
}
tail.next = node;
tail = node;
}
tail.next = null;
return newHead
}
Перевернуть связанный список II
样例
给出链表1->2->3->4->5->null， m = 2 和n = 4，返回1->4->3->2->5->null
挑战
在原地一次翻转完成
Сначала найдите начальный узел и конечный узел, которые нужно поменять местами, затем используйте стек в обратном порядке и в обратном порядке, и, наконец, вставьте обратную ссылку в исходный связанный список.
const reverseBetween = function (head, m, n) {
let node = head, stack = createStack();
for (let i = 1; i < m-1; i++) {
node = node.next;
}
let tail = null;
if (m != 1) {
tail = node;
node = node.next;
}
for (let i = m; i <= n; i++) {
stack.push(node)
node = node.next;
}
while (!stack.isEmpty()) {
let node = stack.pop();
if (!tail) {
tail = node;
head=node
}
tail.next = node;
tail = node;
}
tail.next = node;
return head
}
Суммирование связанных списков II
样例
给出 6->1->7 + 2->9->5。即，617 + 295。
返回 9->1->2。即，912 。
Обратите внимание, что этот вопрос нельзя выполнить, 617+295=912, а затем превратить 912 в связанный список, из-за проблемы, когда связанный список достаточно длинный, целочисленное значение, полученное JS, переполнится. Правильное решение проблемы заключается в том, что идея состоит в том, чтобы инвертировать связанный список, а затем суммировать соответствующие узлы, чтобы получить окончательный связанный список.
const addLists2 = function (l1, l2) {
let newL1 = reverse(l1);
let newL2 = reverse(l2);
let flag = 0, stack = createStack();
while (newL1 && newL2) {
let val1 = newL1.val;
let val2 = newL2.val;
let sum = val1 + val2 + flag;
if (sum >=10) {
flag = 1;
sum = sum-10
} else {
flag = 0;
}
stack.push(sum);
newL1 = newL1.next;
newL2 = newL2.next;
}
let reserve = newL1 ? newL1:newL2;
if (reserve){
reserve.val = reserve.val +flag;
}else {
if (flag) {
stack.push(flag)
}
}
while (reserve) {
stack.push(reserve.val)
reserve = reserve.next;
}
let head = null, tail = null;
while (!stack.isEmpty()) {
let node = new ListNode(stack.pop());
if (!head) {
tail = head = node;
} else {
tail.next = node;
tail = node;
}
}
return head;
}
Объединить два отсортированных связанных списка
样例
给出 1->3->8->11->15->null，2->null， 返回 1->2->3->8->11->15->null。
Эта проблема очень проста: сравните значение узла двух ссылок в цикле while, поместите его в новый связанный список и переместите его на один бит назад, пока один из связанных списков не станет пустым.
const mergeTwoLists = function (l1, l2) {
let l = null, tail = null;
if (!l1) {
return l2
} else if (!l2) {
return l1
}
while (l1 != null && l2 != null) {
let node = null;
if (l1.val < l2.val) {
node = l1;
l1 = l1.next;
} else {
node = l2;
l2 = l2.next;
}
if (!l) {
l = node;
tail = node;
} else {
tail.next = node;
tail = node;
}
}
let remain = l1 ? l1 :l2;
while (remain) {
tail.next = remain;
tail = remain;
remain = remain.next
}
return l
}
удалить элемент из связанного списка
样例
给出链表 1->2->3->3->4->5->3, 和 val = 3, 你需要返回删除3之后的链表：1->2->4->5
При обнаружении значения, которое необходимо удалить, достаточно сказать, что предыдущий узел должен быть следующим, а текущий узел должен быть следующим.
const removeElements = function (head, val) {
let node = head, preNode = head;
while (node) {
if (node.val == val) {
if (node == head && head) {
head = head.next;
node = head
continue
} else {
preNode.next = node.next;
node = node.next;
continue
}
}
preNode = node;
node = node.next;
}
return head
}
Скопировать связанный список со случайным указателем
描述
给出一个链表，每个节点包含一个额外增加的随机指针可以指向链表中的任何节点或空的节点。
返回一个深拷贝的链表。
Эта проблема в основном связана со случайными указателями.Вы можете найти узел, соответствующий случайному указателю, с помощью хэш-сопоставления.
const copyRandomList = function (l1) {
let l2 = null, tail2 = null, node1 = l1; hash = new Map();
// 忽略random对l1进行复制
while (node1) {
if (!l2) {
l2 = tail2 = node1
} else {
tail2.next = node1;
tail2 = node1;
}
hash.set(node1, tail2);
node1 = node1.next
}
while (l2 && l1) {
l2.random = hash.get(l1.random)
l2 = l2.next;
}
return l2
}