Связный список. Поиск середины

В этом уроке ты

Решишь популярную задачу с собеседований.
Научишься применять технику «быстрого и медленного указателя» для связного списка.

Пример задачи с собеседования

И вот ты снова на собеседовании. Интервьюер уже приготовил для тебя задачку на 20 минут и оглашает условие…

Условие

Дан указатель на голову односвязного списка head. Нужно вернуть значение узла, который находится в середине списка. Если число элементов чётное, то вернуть значение того из центральных узлов, который находится дальше от головы.

Пример 1

Ввод: head=[1,2,3,4,5]
Вывод: 3

Пример 2

Ввод: head=[1,2,3,4,5,6]
Вывод: 4
Объяснение: центральными узлами являются 3 и 4, возвращаем 4, так как он дальше от головы.

В чем сложность задачи

Самое простое решение – пройтись по списку два раза. В первый раз вычисляем длину, во второй – находим центральный узел, зная длину.

// class ListNode {
//     public int Val { get; set; }  // Значение узла
//     public ListNode Next { get; set; }  // Ссылка на следующий узел

//     // Конструктор для создания узла с заданным значением
//     public ListNode(int x) {
//         Val = x;
//         Next = null;
//     }
// }

class Solution {
    public ListNode MiddleNodeValue(ListNode head) {
        // Первый проход: подсчет длины списка
        int length = 0;
        ListNode curr = head;
        while (curr != null) {
            length++;
            curr = curr.Next;
        }

        // Второй проход: найти центральный элемент
        int mid_index = length / 2;
        curr = head;
        for (int i = 0; i < mid_index; i++) {
            curr = curr.Next;
        }
        return curr.Val;
    }
}

// class ListNode {
//     public int Val { get; set; }  // Значение узла
//     public ListNode Next { get; set; }  // Ссылка на следующий узел

//     // Конструктор для создания узла с заданным значением
//     public ListNode(int x) {
//         Val = x;
//         Next = null;
//     }
// }

class Solution {
    public ListNode MiddleNodeValue(ListNode head) {
        // Первый проход: подсчет длины списка
        int length = 0;
        ListNode curr = head;
        while (curr != null) {
            length++;
            curr = curr.Next;
        }

        // Второй проход: найти центральный элемент
        int mid_index = length / 2;
        curr = head;
        for (int i = 0; i < mid_index; i++) {
            curr = curr.Next;
        }
        return curr.Val;
    }
}

#include <bits/stdc++.h>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

// Время: O(n)
// Память: O(1)
ListNode* middleNodeValue(ListNode* head) {
    // Первый проход: подсчет длины списка
    int length = 0;
    ListNode* curr = head;
    while (curr) {
        length++;
        curr = curr->next;
    }

    // Второй проход: найти центральный элемент
    int mid_index = length / 2;
    curr = head;
    for (int i = 0; i < mid_index; i++) {
        curr = curr->next;
    }
    return curr->val;
}

package main

// type ListNode struct {
//     Val  int
//     Next *ListNode
// }

// Время: O(n)
// Память: O(1)
func middleNodeValue(head *ListNode) *ListNode {
    // Первый проход: подсчет длины списка
    length := 0
    curr := head
    for curr != nil {
        length++
        curr = curr.Next
    }

    // Второй проход: найти центральный элемент
    midIndex := length / 2
    curr = head
    for i := 0; i < midIndex; i++ {
        curr = curr.Next
    }
    return curr.Val
}

// class ListNode {
//     constructor(val=0, next=null) {
//         this.val = val;
//         this.next = next;
//     }
// }

// Время: O(n)
// Память: O(1)
function middleNodeValue(head) {
    // Первый проход: подсчет длины списка
    let length = 0;
    let curr = head;
    while (curr !== null) {
        length++;
        curr = curr.next;
    }

    // Второй проход: найти центральный элемент
    const mid_index = Math.floor(length / 2);
    curr = head;
    for (let i = 0; i < mid_index; i++) {
        curr = curr.next;
    }
    return curr.val;
}

# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

# Время: O(n)
# Память: O(1)
def middle_node_value(head: ListNode) -> ListNode:
    # Первый проход: подсчет длины списка
    length = 0
    curr = head
    while curr:
        length += 1
        curr = curr.next

    # Второй проход: найти центральный элемент
    mid_index = length // 2
    curr = head
    for _ in range(mid_index):
        curr = curr.next
    return curr.val

Решение оптимально и занимает по времени O(n) и по памяти O(1), но на собеседовании часто ожидают другой подход.

Быстрый и медленный указатель

Техника «быстрого и медленного указателя» — классический приём в связных списках, где используются два указателя: один двигается по списку на один элемент вперёд за раз, а другой – на два. Когда быстрый указатель дойдёт до конца списка, медленный окажется в середине.

// class ListNode {
//     public int Val { get; set; }  // Значение узла
//     public ListNode Next { get; set; }  // Ссылка на следующий узел

//     // Конструктор для создания узла с заданным значением
//     public ListNode(int x) {
//         Val = x;
//         Next = null;
//     }
// }

class Solution {
    // Время: O(n)
    // Память: O(1)
    public ListNode MiddleNodeValue(ListNode head) {
        ListNode slow = head; // двигается на 1 вперед
        ListNode fast = head; // двигается на 2 вперед
        while (fast != null && fast.Next != null) {
            slow = slow.Next;
            fast = fast.Next.Next;
        }
        return slow;
    }
}

#include <bits/stdc++.h>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

// Время: O(n)
// Память: O(1)
ListNode* middleNodeValue(ListNode* head) {
    ListNode* slow = head; // двигается на 1 вперед
    ListNode* fast = head; // двигается на 2 вперед
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

package main

// type ListNode struct {
//     Val  int
//     Next *ListNode
// }

// Время: O(n)
// Память: O(1)
func middleNodeValue(head *ListNode) *ListNode {
    slow := head // двигается на 1 вперед
    fast := head // двигается на 2 вперед
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    return slow
}

package main

// type ListNode struct {
//     Val  int
//     Next *ListNode
// }

// Время: O(n)
// Память: O(1)
func middleNodeValue(head *ListNode) *ListNode {
    slow := head // двигается на 1 вперед
    fast := head // двигается на 2 вперед
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    return slow
}

// class ListNode {
//     int val;
//     ListNode next;
//     ListNode(int x) {
//         val = x;
//         next = null;
//     }
// }

// Время: O(n)
// Память: O(1)
class Solution {
    public ListNode middleNodeValue(ListNode head) {
        ListNode slow = head; // двигается на 1 вперед
        ListNode fast = head; // двигается на 2 вперед
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

# Время: O(n)
# Память: O(1)
def middle_node_value(head: ListNode) -> ListNode:
    slow = head # двигается на 1 вперед
    fast = head # двигается на 2 вперед
    while fast != None and fast.next != None:
        slow = slow.next
        fast = fast.next.next
    return slow

Чтобы было проще понять, почему это работает, давай посмотрим на иллюстрацию, где оранжевым обозначен быстрый указатель, смещающийся всегда на 2 вершины, и медленный, который всегда смещается на одну.

Почему это работает: пока быстрый указатель проходит весь список, медленный проходит только половину. Таким образом, по достижении конца быстрым указателем, медленный окажется в центре.

Совет из практики

Если на собеседовании забыл технику с быстрым и медленным указателем, можно использовать решение через подсчёт длины. Лучше так, чем не решить вовсе.

Что дальше

Попробуй самостоятельно реализовать эту задачу, чтобы закрепить понимание. Это поможет тебе в будущих собеседованиях.