В этом уроке ты
- Научишься работать со связным списком.
- Решишь одну из самых популярных задач на односвязный список с собеседований.
- Узнаешь о времени и затратах памяти для операций над связным списком.
Что такое связный список
Односвязный список — это структура данных, где каждый элемент (узел) хранит данные и ссылку (указатель) на следующий узел. Таким образом элементы соединены друг с другом последовательно, как звенья цепи.
Пример создания связного списка в коде (на рисунке выше показана визуализация):
class Node
{
public int Data { get; } // Данные узла
public Node Next { get; } // Ссылка на следующий узел
public Node(int data, Node next)
{
Data = data;
Next = next;
}
}
// Пример использования
var head = new Node(1, new Node(2, new Node(3, null)));class Node {
public:
int data; // Данные узла
Node* next; // Ссылка на следующий узел
Node(int data, Node* next = nullptr) {
this->data = data;
this->next = next;
}
};
int main() {
// Создаем список: 1 -> 2 -> 3
Node* head = new Node(1, new Node(2, new Node(3, nullptr)));
return 0;
}class Node {
public:
int data; // Данные узла
Node* next; // Ссылка на следующий узел
Node(int data, Node* next = nullptr) {
this->data = data;
this->next = next;
}
};
int main() {
// Создаем список: 1 -> 2 -> 3
Node* head = new Node(1, new Node(2, new Node(3, nullptr)));
return 0;
}package main
type Node struct {
data int // Данные узла
next *Node // Ссылка на следующий узел
}
func main() {
// Создаем список: 1 -> 2 -> 3
head := &Node{1, &Node{2, &Node{3, nil}}}
}class Node {
int data; // Данные узла
Node next; // Ссылка на следующий узел
public Node(int data, Node next) {
this.data = data;
this.next = next;
}
public static void main(String[] args) {
// Создаем список: 1 -> 2 -> 3
Node head = new Node(1, new Node(2, new Node(3, null)));
}
}class Node:
def __init__(self, data, next):
self.data = data # Данные узла
self.next = next # Ссылка на следующий узел
# Создаем список: 1 -> 2 -> 3
head = Node(1, Node(2, Node(3, None)))- Голова (head) — это первый узел списка (в примере узел со значением 1).
- Узел — любой элемент списка (например, 1, 2 или 3).
- Хвост — последний узел в списке, у которого нет ссылки на следующий элемент.
Операции в связном списке
Некоторые операции в связном списке работают эффективнее, чем в массиве. Например, вставка в начало списка занимает O(1), тогда как в массиве это в среднем O(n).
Связный список на собеседовании
На собеседованиях часто предполагается, что связный список уже дан, а твоя задача — выполнить над ним некую операцию: развернуть, найти середину или выполнить другую трансформацию. При этом у тебя обычно есть только голова списка.
Задачи на связный список чаще всего сводятся к аккуратному манипулированию указателями. Хотя они несложны концептуально, требуется внимательность. Чтобы в стрессовой ситуации не растеряться, давай разберем одну из самых популярных задач — разворот связного списка.
На собеседовании у тебя не будет вспомогательных методов. Например, чтобы узнать размер списка, придется написать алгоритм самому, а поиск длины займет O(n) по времени.
Пример задачи с собеседования
Представь, что ты уже на собеседовании в компанию своей мечты и у тебя есть 20 минут на решение задачи, а интервьюер уже озвучивает условие…
Условие
Дана голова односвязного списка head. Нужно развернуть связный список и вернуть новую голову списка.
Пример 1
Ввод: head=[1,2,3,4,5] Вывод: [5,4,3,2,1]
Пример 2
Ввод: head=[1,2,3,4] Вывод: [4,3,2,1]
В чем сложность задачи
Если никогда не решал такие задачи, может возникнуть соблазн сначала преобразовать список в массив, развернуть массив, а потом записать значения обратно в список:
package main
// ListNode представляет узел списка
type ListNode struct {
Val int // Значение узла
Next *ListNode // Ссылка на следующий узел
}
// Время: O(n)
// Память: O(n)
func reverseList(head *ListNode) *ListNode {
// Если список пуст или содержит один элемент, возвращаем его же
if head == nil || head.Next == nil {
return head
}
// Шаг 1: Сохраняем значения в массив
var values []int
current := head
for current != nil {
values = append(values, current.Val)
current = current.Next
}
// Шаг 2: Разворачиваем массив
for i, j := 0, len(values)-1; i < j; i, j = i+1, j-1 {
values[i], values[j] = values[j], values[i]
}
// Шаг 3: Переписываем значения обратно в список
current = head
for _, val := range values {
current.Val = val
current = current.Next
}
return head
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class ListNode {
public:
int val; // Значение узла
ListNode* next; // Ссылка на следующий узел
ListNode(int val = 0, ListNode* next = nullptr) {
this->val = val;
this->next = next;
}
};
// Время: O(n)
// Память: O(n)
ListNode* reverseList(ListNode* head) {
// Если список пуст или содержит один элемент, возвращаем его же
if (!head || !head->next) {
return head;
}
// Шаг 1: Сохраняем значения в массив
vector<int> values;
ListNode* current = head;
while (current) {
values.push_back(current->val);
current = current->next;
}
// Шаг 2: Разворачиваем массив
reverse(values.begin(), values.end());
// Шаг 3: Переписываем значения обратно в список
current = head;
for (int val : values) {
current->val = val;
current = current->next;
}
return head;
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class ListNode {
public:
int val; // Значение узла
ListNode* next; // Ссылка на следующий узел
ListNode(int val = 0, ListNode* next = nullptr) {
this->val = val;
this->next = next;
}
};
// Время: O(n)
// Память: O(n)
ListNode* reverseList(ListNode* head) {
// Если список пуст или содержит один элемент, возвращаем его же
if (!head || !head->next) {
return head;
}
// Шаг 1: Сохраняем значения в массив
vector<int> values;
ListNode* current = head;
while (current) {
values.push_back(current->val);
current = current->next;
}
// Шаг 2: Разворачиваем массив
reverse(values.begin(), values.end());
// Шаг 3: Переписываем значения обратно в список
current = head;
for (int val : values) {
current->val = val;
current = current->next;
}
return head;
}package main
// ListNode представляет узел списка
type ListNode struct {
Val int // Значение узла
Next *ListNode // Ссылка на следующий узел
}
// Время: O(n)
// Память: O(n)
func reverseList(head *ListNode) *ListNode {
// Если список пуст или содержит один элемент, возвращаем его же
if head == nil || head.Next == nil {
return head
}
// Шаг 1: Сохраняем значения в массив
var values []int
current := head
for current != nil {
values = append(values, current.Val)
current = current.Next
}
// Шаг 2: Разворачиваем массив
for i, j := 0, len(values)-1; i < j; i, j = i+1, j-1 {
values[i], values[j] = values[j], values[i]
}
// Шаг 3: Переписываем значения обратно в список
current = head
for _, val := range values {
current.Val = val
current = current.Next
}
return head
}# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
# Время: O(n)
# Память: O(n)
def reverse_list(head: ListNode) -> ListNode:
# Если список пуст или содержит один элемент, возвращаем его же
if not head or not head.next:
return head
# Шаг 1: Сохраняем значения в массив
values = []
current = head
while current:
values.append(current.val)
current = current.next
# Шаг 2: Разворачиваем массив
values.reverse()
# Шаг 3: Переписываем значения обратно в список
current = head
for val in values:
current.val = val
current = current.next
return headclass ListNode {
constructor(val = 0, next = null) {
this.val = val; // Значение узла
this.next = next; // Ссылка на следующий узел
}
}
// Время: O(n)
// Память: O(n)
function reverseList(head) {
// Если список пуст или содержит один элемент, возвращаем его же
if (head === null || head.next === null) {
return head;
}
// Шаг 1: Сохраняем значения в массив
const values = [];
let current = head;
while (current !== null) {
values.push(current.val);
current = current.next;
}
// Шаг 2: Разворачиваем массив
values.reverse();
// Шаг 3: Переписываем значения обратно в список
current = head;
for (const val of values) {
current.val = val;
current = current.next;
}
return head;
}Это решение неэффективно по памяти O(n) и интервьюер точно попросит решить задачу без дополнительной памяти.
Оптимальное решение
Оптимальный способ — менять ссылки “на лету”. Вместо копирования данных в массив и обратно, мы будем последовательно перенаправлять указатели у каждого узла:
class ListNode
{
public int Val { get; set; } // Значение узла
public ListNode Next { get; set; } // Ссылка на следующий узел
public ListNode() { }
public ListNode(int val)
{
Val = val;
Next = null;
}
public ListNode(int val, ListNode next)
{
Val = val;
Next = next;
}
// Время: O(n)
// Память: O(1)
public static ListNode ReverseList(ListNode head)
{
ListNode prev = null; // Предыдущий узел
ListNode curr = head; // Текущий узел
while (curr != null)
{
ListNode tmp = curr.Next; // Сохраняем следующий узел
curr.Next = prev; // Меняем направление ссылки
prev = curr; // Перемещаем prev вперед
curr = tmp; // Перемещаем curr вперед
}
return prev; // Новая голова списка
}
}#include <iostream>
// Определение класса ListNode
class ListNode {
public:
int val; // Значение узла
ListNode* next; // Ссылка на следующий узел
ListNode(int val = 0, ListNode* next = nullptr) {
this->val = val;
this->next = next;
}
};
// Время: O(n)
// Память: O(1)
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr; // Предыдущий узел
ListNode* curr = head; // Текущий узел
while (curr != nullptr) {
ListNode* tmp = curr->next; // Сохраняем следующий узел
curr->next = prev; // Меняем направление ссылки
prev = curr; // Перемещаем prev вперед
curr = tmp; // Перемещаем curr вперед
}
return prev; // Новая голова списка
}package main
import (
"fmt"
)
// ListNode представляет узел списка
type ListNode struct {
Val int // Значение узла
Next *ListNode // Ссылка на следующий узел
}
// Время: O(n)
// Память: O(1)
func reverseList(head *ListNode) *ListNode {
var prev *ListNode = nil // Предыдущий узел
curr := head // Текущий узел
for curr != nil {
tmp := curr.Next // Сохраняем следующий узел
curr.Next = prev // Меняем направление ссылки
prev = curr // Перемещаем prev вперед
curr = tmp // Перемещаем curr вперед
}
return prev // Новая голова списка
}package main
import (
"fmt"
)
// ListNode представляет узел списка
type ListNode struct {
Val int // Значение узла
Next *ListNode // Ссылка на следующий узел
}
// Время: O(n)
// Память: O(1)
func reverseList(head *ListNode) *ListNode {
var prev *ListNode = nil // Предыдущий узел
curr := head // Текущий узел
for curr != nil {
tmp := curr.Next // Сохраняем следующий узел
curr.Next = prev // Меняем направление ссылки
prev = curr // Перемещаем prev вперед
curr = tmp // Перемещаем curr вперед
}
return prev // Новая голова списка
}package main
import (
"fmt"
)
// ListNode представляет узел списка
type ListNode struct {
Val int // Значение узла
Next *ListNode // Ссылка на следующий узел
}
// Время: O(n)
// Память: O(1)
func reverseList(head *ListNode) *ListNode {
var prev *ListNode = nil // Предыдущий узел
curr := head // Текущий узел
for curr != nil {
tmp := curr.Next // Сохраняем следующий узел
curr.Next = prev // Меняем направление ссылки
prev = curr // Перемещаем prev вперед
curr = tmp // Перемещаем curr вперед
}
return prev // Новая голова списка
}package main
import (
"fmt"
)
// ListNode представляет узел списка
type ListNode struct {
Val int // Значение узла
Next *ListNode // Ссылка на следующий узел
}
// Время: O(n)
// Память: O(1)
func reverseList(head *ListNode) *ListNode {
var prev *ListNode = nil // Предыдущий узел
curr := head // Текущий узел
for curr != nil {
tmp := curr.Next // Сохраняем следующий узел
curr.Next = prev // Меняем направление ссылки
prev = curr // Перемещаем prev вперед
curr = tmp // Перемещаем curr вперед
}
return prev // Новая голова списка
}Чтобы лучше понять решение, посмотри как формируется ответ для примера head=[1,2,3,4]. Код выше полностью совпадает с иллюстрацией. Для простоты восприятия нарисовано начальное состояние и состояние на конец каждой итерации цикла
Что дальше
Мы разобрали одну из базовых задач на связный список, на основе которой решается множество других задач. Еще одной базовой задачей является “поиск середины связного списка”. Скорее переходи к ее разбору!