В этом уроке ты
- Научишься применять паттерн «фиктивный узел», чтобы избежать лишнего кода.
Паттерн “фиктивный узел”
Фиктивный узел — это паттерн, позволяющий решить всего одну проблему: избавиться от дублирования кода/лишнего кода. Примеры применения:
- В задаче на удаление вершины обрабатывать удаление первой вершины так же, как и всех остальных, избегая дополнительной проверки.
- В задаче по формированию нового связного списка избежать лишнего кода при выборе первой вершины, к которой будет крепиться ответ.
В чем заключается паттерн
Нужно создать пустую вершину и следующей вершиной указать head, а при возвращении ответа учесть, что была создана фейковая вершина.
// class ListNode {
// public int Val { get; set; }
// public ListNode Next { get; set; }
// public ListNode(int x) { Val = x; }
// public ListNode(int x, ListNode nxt) { Val = x; Next = nxt; }
// }
class Solution {
public ListNode SomeFunc(ListNode head) {
ListNode dummy = new ListNode(0, head); // Создаем фиктивный узел, который указывает на head
// работаем с dummy как с новой головой списка
// ...
// в конце убираем dummy вершину, возвращая dummy.Next как новый head
return dummy.Next;
}
}#include <bits/stdc++.h>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x, ListNode* nxt = NULL) : val(x), next(nxt) {}
};
ListNode* someFunc(ListNode* head) {
ListNode* dummy = new ListNode(0, head);
// работаем с dummy как с новой головой списка
// ...
// Освобождаем dummy перед возвратом результата
ListNode* result = dummy->next;
delete dummy;
return result;
}package main
// type ListNode struct {
// Val int
// Next *ListNode
// }
func someFunc(head *ListNode) *ListNode {
dummy := &ListNode{Val: 0, Next: head}
// работаем с dummy как с новой головой списка
// ...
// в конце убираем dummy вершину
return dummy.Next
}`// class ListNode {
// int val;
// ListNode next;
// ListNode(int x) { val = x; }
// ListNode(int x, ListNode nxt) { val = x; next = nxt; }
// }
class Solution {
public ListNode someFunc(ListNode head) {
ListNode dummy = new ListNode(0, head);
// работаем с dummy как с новой головой списка
// ...
// в конце убираем dummy вершину
return dummy.next;
}
}# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
def some_func(head: ListNode) -> ListNode:
dummy = ListNode(0, head)
# работаем с dummy как с новой головой списка
...
# в конце убираем dummy вершину
return dummy.next // class ListNode {
// constructor(val=0, next=null) {
// this.val = val;
// this.next = next;
// }
// }
function someFunc(head) {
let dummy = new ListNode(0, head);
// работаем с dummy как с новой головой списка
// ...
// в конце убираем dummy вершину
return dummy.next;
}Что дальше
Попробуй решить задачки на тему фейковой вершины самостоятельно, чтобы закрепить всё на практике.