предисловие
Связанный список в структуре данных по-прежнему очень важен, поэтому в этой главе обобщены связанные темы в предложении меча и LeetCode, и мы поделимся ими с вами 🤭
Честно говоря, иногда немного сложно ясно излагать свои мысли, но он грубый парень, который не очень хорошо пишет.Для некоторых концептуальных проблем лучше процитировать объяснение в другом месте, так что я надеюсь, что все поняли .
О временной сложности и пространственной сложности, если вы мало что знаете об этом, вы можете прочитать следующую статью.
Временная и пространственная сложность алгоритма (понять с первого взгляда)
Кодировать слова непросто, вам пригодится, лайк и поддержка
Тема связанного списка будет включена в GitHub с идеями и кодами, и заинтересованные друзья могут прийти и поиграть👇
Структура данных — связанный список
Связанный список
Распространенной базовой структурой данных также является линейная таблица, но она хранит данные не в порядке линейной таблицы, а хранит в каждом узле указатель (Pointer) на следующий узел.
Связанные списки могут достигать сложности O(1) при вставке, что намного быстрее, чем другой линейный список, последовательный список, но требуется O(n) времени, чтобы найти узел или посетить узел с определенным номером, в то время как последовательные списки соответствующая временная сложность таблицы составляет O (log n) и O (1) соответственно.
Преимущества и недостатки:
❝Использование структуры списка может преодолеть недостатки предварительного знания размера данных списка массивов, структура цепочки может использовать компьютерную память, гибкое управление динамической памятью. Но мы потеряли преимущество случайного чтения массива связанных списков, в то время как список из-за увеличения установленной точки целевого домена, накладные расходы пространства относительно велики.
❞
"Связанные списки позволяют вставлять и удалять узлы в любом месте списка, но произвольный доступ запрещен."
Существует множество различных типов связанных списков:
- Односвязный список
- Двусвязный список
- Круговой связанный список
Связанные списки обычно могут быть получены из циклических связанных списков, статических связанных списков, двусвязных списков и т. д. Для использования связанного списка необходимо обратить внимание"головной узел"использование.
class ListNode {
constructor(val) {
this.val = val;
this.next = null;
}
}
//单链表插入、删除、查找
class LinkedList {
constructor(val) {
val = val === undefined ? 'head' : val;
this.head = new ListNode(val)
}
// 找val值节点，没有找到返回-1
findByVal(val) {
let current = this.head
while (current !== null && current.val !== val) {
current = current.next
}
return current ? current : -1
}
// 插入节点,在值为val后面插入
insert(newVal, val) {
let current = this.findByVal(val)
if (current === -1) return false
let newNode = new ListNode(newVal)
newNode.next = current.next
current.next = newNode
}
// 获取值为nodeVal的前一个节点,找不到为-1,参数是val
// 适用于链表中无重复节点
findNodePreByVal(nodeVal) {
let current = this.head;
while (current.next !== null && current.next.val !== nodeVal)
current = current.next
return current !== null ? current : -1
}
// 根据index查找当前节点, 参数为index
// 可以作为比较链表是否有重复节点
findByIndex(index) {
let current = this.head,
pos = 1
while (current.next !== null && pos !== index) {
current = current.next
pos++
}
return (current && pos === index) ? current : -1
}
// 删除某一个节点,删除失败放回false
remove(nodeVal) {
if(nodeVal === 'head') return false
let needRemoveNode = this.findByVal(nodeVal)
if (needRemoveNode === -1) return false
let preveNode = this.findNodePreByVal(nodeVal)
preveNode.next = needRemoveNode.next
}
//遍历节点
disPlay() {
let res = new Array()
let current = this.head
while (current !== null) {
res.push(current.val)
current = current.next
}
return res
}
// 在链表末尾插入一个新的节点
push(nodeVal) {
let current = this.head
let node = new ListNode(nodeVal)
while (current.next !== null)
current = current.next
current.next = node
}
// 在头部插入
frontPush(nodeVal) {
let newNode = new ListNode(nodeVal)
this.insert(nodeVal,'head')
}
}
Конечно, могут быть еще какие-то способы, о которых я не подумал, а остальное можно сделать самому
"Использование класса связанного списка"
let demo = new LinkedList() // LinkedList {head: ListNode}
// console.log((demo.disPlay()))
demo.push('1232')
demo.insert(123, 'head');
demo.push('last value')
demo.frontPush('start')
demo.remove('head')
// demo.remove('last value')
// console.log(demo.remove('head'))
// demo.push('2132')
// demo.insert('不存在的值', '插入失败') //return -1
console.log(demo.findByIndex(1))
console.log((demo.disPlay()))
Приведенные выше фрагменты кода используются для тестирования.После тестирования в основном нет серьезных проблем, указанных выше.Конечно, на некоторые детали все же необходимо обратить внимание, напримерfindByIndexв этой функцииpos = 0ещеpos = 1Вопрос зависит от вас, и если да,removeМожет ли функция удалить головной узел «голова», точного стандарта нет, это можно определить в соответствии с вашей собственной ситуацией,
Просто имейте в виду, что это не единственный критерий, если вы думаете, что можете удалить «голову», это нормально.
"Двусвязный список"
Аналогично работают двусвязные списки, но还有一个引用字段, называется“prev”поле. С помощью этого дополнительного поля вы можете узнать предыдущий узел текущего узла.
Давайте посмотрим пример:
Зеленые стрелки показывают, как работает наше поле «предыдущий».
"Похожая структура 👇"
class doubleLinkNode {
constructor (val) {
this.val = val
this.prev = null
this.next = null
}
}
Подобно односвязному списку, мы будем использовать头结点для представления всего списка.
Для вставок и удалений это немного сложнее, чем односвязный список, потому что нам также нужно иметь дело с полем «предыдущий».
"Добавить операцию — двусвязный список"
Например, конечно, лучшая форма - нарисовать картинку, чтобы решить ее.
Давайте добавим новый узел 9 после существующего узла 6:
Первый шаг: ссылкаcur(узел 9) иprev(узел 6) иnext(узел 15)
Шаг 2: используйтеcur(Узел 9) Пересвязатьprev(узел 6) иnext(узел 15)
"Поэтому при выполнении вопросов со связанными списками самое главное — это рисунок, после которого появится код."
Остается вопрос, хотим ли мы开头или结尾Как вставить новый узел?
"Операция удаления — двусвязный список"
Берите пример 👇
Наша цель — удалить узел из двусвязного списка 6
Итак, мы связываем его предыдущий узел 23 со следующим узлом 15:
Узел 6 больше не входит в наш двусвязный список.
оставить вопрос: если бы мы удалили第一个结点или最后一个结点Как сделать?
рисунок 🤭
Мне не нужно писать код, многие люди могут кодировать в Интернете, вы можете увидеть, как это пишут другие.
резюме
Кратко рассмотрим производительность односвязных и двусвязных списков.
Они похожи во многих операциях
- они могут все
在 O(1) 时间内删除第一个结点. - они могут все
在 O(1) 时间内在给定结点之后或列表开头添加一个新结点. - Ни один из них не может работать в постоянное время
随机访问数据.
Но есть небольшая разница при удалении данного узла (включая последний).
- В односвязном списке он не может получить предыдущий узел данного узла, поэтому мы должны потратить перед удалением данного узла
O(N)время, чтобы найти предыдущий узел. - В двухсвященном списке будет проще, потому что мы можем использовать поле «Ранее», прежде чем приобретать узел. Так что мы можем
O(1)Удалить данный узел вовремя.
Сравнивать связанные списки с другими структурами данных (массивами, очередями, стеками)时间复杂度Сравнение:
После этого сравнения нам нетрудно сделать следующие выводы:
❝Если вам нужно часто добавлять или удалять узлы, хорошим выбором может быть связанный список.
Если вам нужно часто обращаться к элементам по индексу, массив может быть лучшим выбором, чем связанный список.
❞
Далее в центре внимания этой статьи.От теории к практике, давайте посмотрим, какие бывают типы вопросов👇
основной тип вопроса
Следующие типы вопросов отсортированы в соответствии с порядком личной чистки, а также будет разделен уровень сложности, вы можете обратиться к нему.
Сайт главных вопросов👇
Объединить два отсортированных связанных списка⭐
Описание заголовка: объединить два восходящих связанных списка в новый"по возрастанию"链表并返回。 Новый связанный список формируется путем соединения всех узлов данных двух связанных списков.
❝Связь:[Likou] Объединить два нумерованных списка
❞
"Пример:"
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
Нерекурсивные идеи:
-
Mock Вопросы + связанный список
-
Идея конечно проста, главное процесс симуляции.С точки зрения алгоритма такого рода вопрос можно более симулировать, симулируя процесс вашего мышления, каждый раз сравнивайте размер двух l1.val и l2.val , возьмите меньшее значение и в то же время обновите меньшее значение, чтобы оно указывало на следующий узел
-
Главное, на что нужно обратить внимание, это условие завершения цикла: когда одно из двух пустое, оно указывает на ноль
-
Наконец, необходимо определить, какой из двух связанных списков не является пустым.Хорошо подключить непустой связанный список к узлу tmp sentinel.
var mergeTwoLists = function (l1, l2) {
let newNode = new ListNode('start'), // 做题套路,头节点
tmp = newNode; // tmp作为哨兵节点
while (l1 && l2) { // 循环结束的条件就是两者都要为非null
if(l1.val >= l2.val) {
tmp.next = l2
l2 = l2.next
}else{
tmp.next = l1
l1 = l1.next
}
tmp = tmp.next // 哨兵节点更新指向下一个节点
}
// 最后需要判断哪个链表还存在非null
tmp.next = l1 == null ? l2 : l1;
return newNode.next;
};
Рекурсивная идея:"Рекурсивное рекурсивное решение Чтобы обратить внимание, что тема в каждом узле должно возвращать значение мало, чтобы убедиться, что список был самым маленьким в начале, мы, наконец, должны получить"
Первоначальный подход заключается в моделировании + связанного списка, но, увидев рекурсивное написание в области обсуждения, определенно лучше его прочитать. По-прежнему очень важно иметь несколько решений вопроса. Это также в определенной степени расходится с мышлением. Мы по-прежнему выступаем за множественность решений.
- Рекурсивный выход: когда какой-либо связанный список пуст, напрямую возвращайте другую ссылку, то есть процесс сплайсинга
- Выньте узлы из двух связанных списков по очереди и сравните меньший узел со следующим узлом связанного списка.
Возвращает k-й последний узел⭐
Название Описание: Алгоритм поиска обратного узла k-way связанного списка. Возвращаемое значение узла.
❝Связь:[Likou] Вернуть k-й узел снизу
❞
Написание двойным указателем 👇
Сделайте два передних и задних указателя, сначала отпустите задний указатель на k, затем два указателя разделены на k шагов и, наконец, пройдите задний указатель Когда задний указатель равен нулю, передний указатель является ответом, потому что в начале , разница между ними составляет k расстояния.
Обратно связанный список⭐
Описание темы: Реверс односвязного списка.
❝Связь:[leetcode] Перевернуть связанный список
❞
"Пример:"
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
Идея: перебрать три указателя prev curr next previous pointer current pointer next pointer
- Каждый раз, когда текущий указатель curr указывает на предыдущий
- next сохраняет информацию о следующем узле
Совет: Установите для узла Sentinel значение null, а для curr — заголовок в начале.
Итеративно извлекает все время, пока текущий узел curr не станет хвостовым узлом
var reverseList = function (head) {
if(!head) return null
let prev = null,
curr = head
while( curr != null) {
let next = curr.next;
curr.next = prev
prev = curr
curr = next
}
return prev
};
рекурсивное письмо
Я уже говорил об этой идее, давайте посмотрим на код между нами.
var reverseList = function(head) {
let reverse = (prev,curr) => {
if(!curr)return prev;
let next = curr.next;
curr.next = prev;
return reverse(curr,next);
}
return reverse(null,head);
};
Интервальная инверсия ⭐⭐
Описание названия: обратная ведомая позицияmприбытьnсвязанный список. Пожалуйста, используйте одно сканирование, чтобы завершить разворот.
"проиллюстрировать:"1 ≤m≤n≤ длины связанного списка.
❝Связь:[leetcode] таблица обратной цепочки II
❞
"Пример:"
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
Как и в предыдущем вопросе, суп не меняет лекарство, поэтому мы все еще можем использовать итеративный подход для завершения.
Необходимо записать два узла, хвостовой и передний узлы
Роль двух узлов заключается в повторном подключении к новому связанному списку после изменения последнего интервала.
var reverseBetween = function (head, m, n) {
let count = n-m,
newNode = new ListNode('head');
tmp = newNode;
tmp.next = head; // 哨兵节点,这样子同时也保证了newNode下一个节点就是head
for(let i = 0; i < m -1; i++ ){
tmp = tmp.next;
}
// 此时循环后,tmp保留的就是反转区间前一个节点,需要用front保留下来
let front, prev, curr,tail;
front = tmp; // 保留的是区间首节点
// 同时tail指针的作用是将反转后的链接到最后节点
prev = tail = tmp.next; // 保留反转后的队尾节点 也就是tail
curr = prev.next
for(let i = 0; i < count; i++ ) {
let next = curr.next;
curr.next = prev;
prev = curr
curr = next
}
// 将原本区间首节点链接到后结点
tail.next = curr
// font是区间前面一个节点,需要链接的就是区间反转的最后一个节点
front.next = prev
return newNode.next // 最后返回newNode.next就行,一开始我们指向了head节点
};
Нажмите здесь, чтобы получить код 🤭
Попарно поменять местами узлы в связанном списке⭐⭐
Описание темы: Учитывая связанный список, поменяйте местами соседние узлы два на два и верните замененный связанный список."Вы не можете просто изменить значение внутри узла", но требует фактической замены узла.
❝Связь:leetcode меняет местами узлы в связанном списке по два
❞
"Пример:"
给定 1->2->3->4, 你应该返回 2->1->4->3.
Идеи итерации, подпрограммы, плюс дозорный узел tmp стук по линии, тоже не понимаю слов, рисование решает все, действительно не понимает слов, посмотрите на эту диаграмму
var swapPairs = function (head) {
let newNode = new ListNode('start');
newNode.next = head, // 链表头节点套路操作
tmp = newNode; // tmp哨兵节点,这里要从newNode节点开始,并不是从head开始的
while( tmp.next !== null && tmp.next.next !== null) {
let start = tmp.next,
end = start.next;
tmp.next = end
start.next = end.next
end.next = start
tmp = start
}
return newNode.next // 返回的自然就是指向 链表头节点的next指针
};
Конечно, во время интервью нужно писать. Вы должны быть в состоянии нарисовать картинку. Легко писать, когда вы смотрите на картинку. Честно говоря, я не могу придумать рекурсивный способ написать это. я такой тупой 🤭
Набор из K перевернутых связанных списков ⭐⭐⭐
Описание заголовка: дать вам связанный список, каждыйkГруппа узлов перевернута, пожалуйста, верните перевернутый связанный список.
Объяснение: k — положительное целое число, значение которого меньше или равно длине связанного списка. Если общее количество узлов неkЦелое число, кратное , затем сохраните последние оставшиеся узлы в исходном порядке.
❝Связь:[Набор из K перевернутых связанных списков](https://leetcode-cn.com/problems/swap-nodes-in-pairs/)
❞
Пример :
给定这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5
Сначала посмотрите на решение, leetcode⭐⭐⭐Если у вас есть проблема, вам не нужно тратить время на ее обдумывание, вы можете посмотреть на идеи других людей, понять идеи других людей и, наконец, преобразовать их в свои собственные идеи. . После просмотра у вас будет прозрение, и вы будете знать, как его достичь.
- Поскольку имеется k групп, для записи количества узлов должен быть счетчик count.
-
startСмысл указателяstartЗаписанная информация представляет собой узел, непосредственно предшествующий положению начального узла текущего пакета. -
endСмысл указателя - следующий узел, который нужно перевернуть. - После перелистывания,
startУказывает на перевернутый связанный список, диапазон（start，end）Последний узел, возвратstartузел. - В это время также необходимо указать последний узел в перевернутой группе на следующую группу, то есть
front.next = cur - То есть значение 1 узла в графе указывает на конец
Возьмем пример,head=[1,2,3,4,5,6,7,8], k = 3
Если вы ее не видите, нарисуйте картинку сами, а затем прочитайте ее несколько раз вместе с кодом.Вы должны прочитать и написать задачу несколько раз, и вы, естественно, почувствуете ее.
"Ключевой момент анализа"
- Создать новый узел
- Сгруппируйте связанный список в k единиц, записывая позиции начального и последнего узла каждой группы.
- Переверните каждую группу соответствующим образом, не забудьте изменить положение
- вернуть newNode.next
var reverseKGroup = (head, k) => {
let reverseList = (start, end) => {
let [pre, cur] = [start, start.next],
front = cur;
// 终止条件就是cur当前节点不能等于end节点
// 翻转的套路
while( cur !== end) {
let next = cur.next
cur.next = pre
pre = cur
cur = next
}
front.next = end // 新翻转链表需要连接,也就是front指向原来区间后一个节点
start.next = pre // 新翻转的开头需要连接start.next
return front // 返回翻转后需要连接链表,也就是front指向
}
let newNode = new ListNode('start')
newNode.next = head;
let [start, end] = [newNode,newNode.next],
count = 0;
while(end !== null ) {
count++
if( count % k === 0) {
// k个节点翻转后,又重新开始,返回值就是end节点前面一个
start = reverseList(start, end.next)
end = start.next
}else{
//不是一个分组就指向下一个节点
end = end.next
}
}
return newNode.next
};
Молодец, во время интервью, если ты попросишь меня написать это, если ты не дашь мне нарисовать картинку, я не смогу ее абстрагировать 💢💢
Объединить K отсортированных связанных списков ⭐⭐⭐
Описание темы: Слияниеkотсортированный связанный список и вернуть объединенный отсортированный связанный список. Пожалуйста, проанализируйте и опишите сложность алгоритма.
❝Связь:[Объединить K отсортированных связанных списков](https://leetcode-cn.com/problems/swap-nodes-in-pairs/)
❞
"Пример:"
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6
[Связанный список палиндромов]⭐
Описание темы: Определите, является ли связанный список связным списком-палиндромом.
❝Связь:LeetCode - Palindrome связан список
❞
"Пример:"
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6
"Пример 1:"
输入: 1->2
输出: false
"Пример 2:"
输入: 1->2->2->1
输出: true
Идеи решения проблемы:
Найдите середину связанного списка, а затем переверните вторую половину, вы можете сравнить и сделать выводы по очереди.
Вопрос в том, как найти середину?
"Быстрый и медленный указатель"
Это слишком широко используется в связанных списках. Идея состоит в том, чтобы установить промежуточный указатель mid. За один обход head перемещается на два пробела, а mid перемещается на один пробел. Когда head получает последнее значение или выскакивает, mid указывает на среднее значение. .
let mid = head
// 循环条件：只要head存在则最少走一次
while(head !== null && head.next !== null) {
head = head.next.next // 指针一次走两格
mid = mid.next// 中间指针一次走一格
}
При обходе связанный список переворачивается путем итерации, и узлы до середины будут перевернуты. Используйте итерацию для обратного.
while(head !== null && head.next !== null) {
pre = mid
mid = mid.next
head = head.next.next
pre.next = reversed
reversed = pre
}
Например:
奇数：1 -> 2 -> 3 -> 2 ->1
遍历完成后：mid = 3->2->1
reversed = 2->1
偶数：1 -> 2 -> 2 ->1
遍历完成后：mid = 2->1
reversed = 2->1
Полный код:
var isPalindrome = function (head) {
if (head === null || head.next === null) return true;
let mid = head,
pre = null,
reversed = null; // reversed翻转的链表
while (head !== null && head.next !== null) {
// 常规翻转的套路
pre = mid
mid = mid.next
head = head.next.next
pre.next = reversed
reversed = pre
}
// 判断链表数是不是奇数,是的话mid往后走一位
if (head) mid = mid.next
while (mid) {
if (reversed.val !== mid.val) return false
reversed = reversed.next
mid = mid.next
}
return true
};
[Пересечение связанного списка]⭐
Описание темы: Имея два (односвязных) списка, определите, пересекаются ли они, и верните пересечение. Обратите внимание, что определение пересечения основано на ссылке узла, а не на значении узла. Другими словами, два связанных списка пересекаются, если k-й узел одного связанного списка является тем же узлом (ссылающимся точно на то же самое), что и j-й узел другого связанного списка.
❝Связь:[пересечение списка, связанного с литкодом]
❞
Пример 1:
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
Пример 2:
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
Пример 3:
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。
Идеи:
- Предоставление двух указателей, каждый указатель после завершения своего пути, указывает на другой список, тогда два узла равны, это должна быть одна и та же точка.
- Поскольку расстояние, пройденное двумя указателями, одинаково, и каждый раз, когда они перемещаются вперед на 1, расстояние равно и скорость одинакова, если они равны, они должны быть одной и той же точкой.
var getIntersectionNode = function (headA, headB) {
let p1 = headA,
p2 = headB;
while (p1 != p2) {
p1 = p1 === null ? headB : p1.next
p2 = p2 === null ? headA : p2.next
}
return p1
};
Бросание кирпичей и привлечение нефрита
Я выбрал некоторые темы, и я надеюсь, что это будет процесс для вас, чтобы привлечь других, и это также краткое изложение меня. Я продолжу чистить вопросы. Если вам нужно продолжать следовать за мной, чтобы чистить вопросы, вы можете взглянуть на следующее 👇
❤️ Всем спасибо
Если вы считаете этот контент полезным:
-
Поставьте лайк и поддержите его, чтобы больше людей увидело этот контент
-
Вы можете поделиться со мной своими мыслями в области комментариев, и вы также можете записать свой мыслительный процесс в области комментариев.
-
Если вы считаете, что это хорошо, вы также можете прочитать предыдущие статьи:
[Полная искренности👍]Советы по отладке Chrome DevTools, эффективность➡️🚀🚀🚀
[Практично 👍] Порекомендуйте несколько отличных интерфейсных веб-сайтов.
[Галантерея👍] От детальной работы массива js до разбора array.js в v8
[1.2W word👍] Читы на девушку - как работает браузер (Часть 1)
[1.1W word] Читы на девушку - как работает браузер (процесс рендеринга)
[Полная искренности✍]Возьмите вас, чтобы заполнить некоторые подверженные ошибкам ямы JS