4.2   Связный список¶

class ListNode:
    """Класс узла связного списка"""
    def __init__(self, val: int):
        self.val: int = val               # Значение узла
        self.next: ListNode | None = None # Ссылка на следующий узел

/* Структура узла связного списка */
struct ListNode {
    int val;         // Значение узла
    ListNode *next;  // Указатель на следующий узел
    ListNode(int x) : val(x), next(nullptr) {}  // Конструктор
};

/* Класс узла связного списка */
class ListNode {
    int val;        // Значение узла
    ListNode next;  // Ссылка на следующий узел
    ListNode(int x) { val = x; }  // Конструктор
}

/* Класс узла связного списка */
class ListNode(int x) {  // Конструктор
    int val = x;         // Значение узла
    ListNode? next;      // Ссылка на следующий узел
}

/* Структура узла связного списка */
type ListNode struct {
    Val  int       // Значение узла
    Next *ListNode // Указатель на следующий узел
}

// NewListNode Конструктор, создает новый связный список
func NewListNode(val int) *ListNode {
    return &ListNode{
        Val:  val,
        Next: nil,
    }
}

/* Класс узла связного списка */
class ListNode {
    var val: Int // Значение узла
    var next: ListNode? // Ссылка на следующий узел

    init(x: Int) { // Конструктор
        val = x
    }
}

/* Класс узла связного списка */
class ListNode {
    constructor(val, next) {
        this.val = (val === undefined ? 0 : val);       // Значение узла
        this.next = (next === undefined ? null : next); // Ссылка на следующий узел
    }
}

/* Класс узла связного списка */
class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = val === undefined ? 0 : val;        // Значение узла
        this.next = next === undefined ? null : next;  // Ссылка на следующий узел
    }
}

/* Класс узла связного списка */
class ListNode {
  int val; // Значение узла
  ListNode? next; // Ссылка на следующий узел
  ListNode(this.val, [this.next]); // Конструктор
}

use std::rc::Rc;
use std::cell::RefCell;
/* Класс узла связного списка */
#[derive(Debug)]
struct ListNode {
    val: i32, // Значение узла
    next: Option<Rc<RefCell<ListNode>>>, // Указатель на следующий узел
}

/* Структура узла связного списка */
typedef struct ListNode {
    int val;               // Значение узла
    struct ListNode *next; // Указатель на следующий узел
} ListNode;

/* Конструктор */
ListNode *newListNode(int val) {
    ListNode *node;
    node = (ListNode *) malloc(sizeof(ListNode));
    node->val = val;
    node->next = NULL;
    return node;
}

/* Класс узла связного списка */
// Конструктор
class ListNode(x: Int) {
    val _val: Int = x          // Значение узла
    val next: ListNode? = null // Ссылка на следующий узел
}

# Класс узла связного списка
class ListNode
  attr_accessor :val  # Значение узла
  attr_accessor :next # Ссылка на следующий узел

  def initialize(val=0, next_node=nil)
    @val = val
    @next = next_node
  end
end

# Инициализация связного списка 1 -> 3 -> 2 -> 5 -> 4
# Инициализация отдельных узлов
n0 = ListNode(1)
n1 = ListNode(3)
n2 = ListNode(2)
n3 = ListNode(5)
n4 = ListNode(4)
# Построение ссылок между узлами
n0.next = n1
n1.next = n2
n2.next = n3
n3.next = n4

/* Инициализация связного списка 1 -> 3 -> 2 -> 5 -> 4 */
// Инициализация отдельных узлов
ListNode* n0 = new ListNode(1);
ListNode* n1 = new ListNode(3);
ListNode* n2 = new ListNode(2);
ListNode* n3 = new ListNode(5);
ListNode* n4 = new ListNode(4);
// Построение ссылок между узлами
n0->next = n1;
n1->next = n2;
n2->next = n3;
n3->next = n4;

/* Инициализация связного списка 1 -> 3 -> 2 -> 5 -> 4 */
// Инициализация отдельных узлов
ListNode n0 = new ListNode(1);
ListNode n1 = new ListNode(3);
ListNode n2 = new ListNode(2);
ListNode n3 = new ListNode(5);
ListNode n4 = new ListNode(4);
// Построение ссылок между узлами
n0.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n4;

/* Инициализация связного списка 1 -> 3 -> 2 -> 5 -> 4 */
// Инициализация отдельных узлов
ListNode n0 = new(1);
ListNode n1 = new(3);
ListNode n2 = new(2);
ListNode n3 = new(5);
ListNode n4 = new(4);
// Построение ссылок между узлами
n0.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n4;

/* Инициализация связного списка 1 -> 3 -> 2 -> 5 -> 4 */
// Инициализация отдельных узлов
n0 := NewListNode(1)
n1 := NewListNode(3)
n2 := NewListNode(2)
n3 := NewListNode(5)
n4 := NewListNode(4)
// Построение ссылок между узлами
n0.Next = n1
n1.Next = n2
n2.Next = n3
n3.Next = n4

/* Инициализация связного списка 1 -> 3 -> 2 -> 5 -> 4 */
// Инициализация отдельных узлов
let n0 = ListNode(x: 1)
let n1 = ListNode(x: 3)
let n2 = ListNode(x: 2)
let n3 = ListNode(x: 5)
let n4 = ListNode(x: 4)
// Построение ссылок между узлами
n0.next = n1
n1.next = n2
n2.next = n3
n3.next = n4

/* Инициализация связного списка 1 -> 3 -> 2 -> 5 -> 4 */
// Инициализация отдельных узлов
const n0 = new ListNode(1);
const n1 = new ListNode(3);
const n2 = new ListNode(2);
const n3 = new ListNode(5);
const n4 = new ListNode(4);
// Построение ссылок между узлами
n0.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n4;

/* Инициализация связного списка 1 -> 3 -> 2 -> 5 -> 4 */
// Инициализация отдельных узлов
const n0 = new ListNode(1);
const n1 = new ListNode(3);
const n2 = new ListNode(2);
const n3 = new ListNode(5);
const n4 = new ListNode(4);
// Построение ссылок между узлами
n0.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n4;

/* Инициализация связного списка 1 -> 3 -> 2 -> 5 -> 4 */\
// Инициализация отдельных узлов
ListNode n0 = ListNode(1);
ListNode n1 = ListNode(3);
ListNode n2 = ListNode(2);
ListNode n3 = ListNode(5);
ListNode n4 = ListNode(4);
// Построение ссылок между узлами
n0.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n4;

/* Инициализация связного списка 1 -> 3 -> 2 -> 5 -> 4 */
// Инициализация отдельных узлов
let n0 = Rc::new(RefCell::new(ListNode { val: 1, next: None }));
let n1 = Rc::new(RefCell::new(ListNode { val: 3, next: None }));
let n2 = Rc::new(RefCell::new(ListNode { val: 2, next: None }));
let n3 = Rc::new(RefCell::new(ListNode { val: 5, next: None }));
let n4 = Rc::new(RefCell::new(ListNode { val: 4, next: None }));

// Построение ссылок между узлами
n0.borrow_mut().next = Some(n1.clone());
n1.borrow_mut().next = Some(n2.clone());
n2.borrow_mut().next = Some(n3.clone());
n3.borrow_mut().next = Some(n4.clone());

/* Инициализация связного списка 1 -> 3 -> 2 -> 5 -> 4 */
// Инициализация отдельных узлов
ListNode* n0 = newListNode(1);
ListNode* n1 = newListNode(3);
ListNode* n2 = newListNode(2);
ListNode* n3 = newListNode(5);
ListNode* n4 = newListNode(4);
// Построение ссылок между узлами
n0->next = n1;
n1->next = n2;
n2->next = n3;
n3->next = n4;

/* Инициализация связного списка 1 -> 3 -> 2 -> 5 -> 4 */
// Инициализация отдельных узлов
val n0 = ListNode(1)
val n1 = ListNode(3)
val n2 = ListNode(2)
val n3 = ListNode(5)
val n4 = ListNode(4)
// Построение ссылок между узлами
n0.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n4;

# Инициализация связного списка 1 -> 3 -> 2 -> 5 -> 4
# Инициализация отдельных узлов
n0 = ListNode.new(1)
n1 = ListNode.new(3)
n2 = ListNode.new(2)
n3 = ListNode.new(5)
n4 = ListNode.new(4)
# Построение ссылок между узлами
n0.next = n1
n1.next = n2
n2.next = n3
n3.next = n4

def insert(n0: ListNode, P: ListNode):
    """Вставить узел P после узла n0 в связном списке"""
    n1 = n0.next
    P.next = n1
    n0.next = P

/* Вставить узел P после узла n0 в связном списке */
void insert(ListNode *n0, ListNode *P) {
    ListNode *n1 = n0->next;
    P->next = n1;
    n0->next = P;
}

/* Вставить узел P после узла n0 в связном списке */
void insert(ListNode n0, ListNode P) {
    ListNode n1 = n0.next;
    P.next = n1;
    n0.next = P;
}

/* Вставить узел P после узла n0 в связном списке */
void Insert(ListNode n0, ListNode P) {
    ListNode? n1 = n0.next;
    P.next = n1;
    n0.next = P;
}

/* Вставить узел P после узла n0 в связном списке */
func insertNode(n0 *ListNode, P *ListNode) {
    n1 := n0.Next
    P.Next = n1
    n0.Next = P
}

/* Вставить узел P после узла n0 в связном списке */
func insert(n0: ListNode, P: ListNode) {
    let n1 = n0.next
    P.next = n1
    n0.next = P
}

/* Вставить узел P после узла n0 в связном списке */
function insert(n0, P) {
    const n1 = n0.next;
    P.next = n1;
    n0.next = P;
}

/* Вставить узел P после узла n0 в связном списке */
function insert(n0: ListNode, P: ListNode): void {
    const n1 = n0.next;
    P.next = n1;
    n0.next = P;
}

/* Вставить узел P после узла n0 в связном списке */
void insert(ListNode n0, ListNode P) {
  ListNode? n1 = n0.next;
  P.next = n1;
  n0.next = P;
}

/* Вставить узел P после узла n0 в связном списке */
#[allow(non_snake_case)]
pub fn insert<T>(n0: &Rc<RefCell<ListNode<T>>>, P: Rc<RefCell<ListNode<T>>>) {
    let n1 = n0.borrow_mut().next.take();
    P.borrow_mut().next = n1;
    n0.borrow_mut().next = Some(P);
}

/* Вставить узел P после узла n0 в связном списке */
void insert(ListNode *n0, ListNode *P) {
    ListNode *n1 = n0->next;
    P->next = n1;
    n0->next = P;
}

/* Вставить узел P после узла n0 в связном списке */
fun insert(n0: ListNode?, p: ListNode?) {
    val n1 = n0?.next
    p?.next = n1
    n0?.next = p
}

### Вставка узла _p после узла n0 в связном списке ###
# В Ruby `p` является встроенной функцией, а `P` — константой, поэтому вместо них можно использовать `_p`
def insert(n0, _p)
  n1 = n0.next
  _p.next = n1
  n0.next = _p
end

def remove(n0: ListNode):
    """Удалить первый узел после узла n0 в связном списке"""
    if not n0.next:
        return
    # n0 -> P -> n1
    P = n0.next
    n1 = P.next
    n0.next = n1

/* Удалить первый узел после узла n0 в связном списке */
void remove(ListNode *n0) {
    if (n0->next == nullptr)
        return;
    // n0 -> P -> n1
    ListNode *P = n0->next;
    ListNode *n1 = P->next;
    n0->next = n1;
    // Освободить память
    delete P;
}

/* Удалить первый узел после узла n0 в связном списке */
void remove(ListNode n0) {
    if (n0.next == null)
        return;
    // n0 -> P -> n1
    ListNode P = n0.next;
    ListNode n1 = P.next;
    n0.next = n1;
}

/* Удалить первый узел после узла n0 в связном списке */
void Remove(ListNode n0) {
    if (n0.next == null)
        return;
    // n0 -> P -> n1
    ListNode P = n0.next;
    ListNode? n1 = P.next;
    n0.next = n1;
}

/* Удалить первый узел после узла n0 в связном списке */
func removeItem(n0 *ListNode) {
    if n0.Next == nil {
        return
    }
    // n0 -> P -> n1
    P := n0.Next
    n1 := P.Next
    n0.Next = n1
}

/* Удалить первый узел после узла n0 в связном списке */
func remove(n0: ListNode) {
    if n0.next == nil {
        return
    }
    // n0 -> P -> n1
    let P = n0.next
    let n1 = P?.next
    n0.next = n1
}

/* Удалить первый узел после узла n0 в связном списке */
function remove(n0) {
    if (!n0.next) return;
    // n0 -> P -> n1
    const P = n0.next;
    const n1 = P.next;
    n0.next = n1;
}

/* Удалить первый узел после узла n0 в связном списке */
function remove(n0: ListNode): void {
    if (!n0.next) {
        return;
    }
    // n0 -> P -> n1
    const P = n0.next;
    const n1 = P.next;
    n0.next = n1;
}

/* Удалить первый узел после узла n0 в связном списке */
void remove(ListNode n0) {
  if (n0.next == null) return;
  // n0 -> P -> n1
  ListNode P = n0.next!;
  ListNode? n1 = P.next;
  n0.next = n1;
}

/* Удалить первый узел после узла n0 в связном списке */
#[allow(non_snake_case)]
pub fn remove<T>(n0: &Rc<RefCell<ListNode<T>>>) {
    // n0 -> P -> n1
    let P = n0.borrow_mut().next.take();
    if let Some(node) = P {
        let n1 = node.borrow_mut().next.take();
        n0.borrow_mut().next = n1;
    }
}

/* Удалить первый узел после узла n0 в связном списке */
// Внимание: stdio.h уже использует ключевое слово remove
void removeItem(ListNode *n0) {
    if (!n0->next)
        return;
    // n0 -> P -> n1
    ListNode *P = n0->next;
    ListNode *n1 = P->next;
    n0->next = n1;
    // Освободить память
    free(P);
}

/* Удалить первый узел после узла n0 в связном списке */
fun remove(n0: ListNode?) {
    if (n0?.next == null)
        return
    // n0 -> P -> n1
    val p = n0.next
    val n1 = p?.next
    n0.next = n1
}

### Удаление первого узла после узла n0 в связном списке ###
def remove(n0)
  return if n0.next.nil?

  # n0 -> remove_node -> n1
  remove_node = n0.next
  n1 = remove_node.next
  n0.next = n1
end

def access(head: ListNode, index: int) -> ListNode | None:
    """Доступ к узлу связного списка по индексу index"""
    for _ in range(index):
        if not head:
            return None
        head = head.next
    return head

/* Доступ к узлу связного списка по индексу index */
ListNode *access(ListNode *head, int index) {
    for (int i = 0; i < index; i++) {
        if (head == nullptr)
            return nullptr;
        head = head->next;
    }
    return head;
}

/* Доступ к узлу связного списка по индексу index */
ListNode access(ListNode head, int index) {
    for (int i = 0; i < index; i++) {
        if (head == null)
            return null;
        head = head.next;
    }
    return head;
}

/* Доступ к узлу связного списка по индексу index */
ListNode? Access(ListNode? head, int index) {
    for (int i = 0; i < index; i++) {
        if (head == null)
            return null;
        head = head.next;
    }
    return head;
}

/* Доступ к узлу связного списка по индексу index */
func access(head *ListNode, index int) *ListNode {
    for i := 0; i < index; i++ {
        if head == nil {
            return nil
        }
        head = head.Next
    }
    return head
}

/* Доступ к узлу связного списка по индексу index */
func access(head: ListNode, index: Int) -> ListNode? {
    var head: ListNode? = head
    for _ in 0 ..< index {
        if head == nil {
            return nil
        }
        head = head?.next
    }
    return head
}

/* Доступ к узлу связного списка по индексу index */
function access(head, index) {
    for (let i = 0; i < index; i++) {
        if (!head) {
            return null;
        }
        head = head.next;
    }
    return head;
}

/* Доступ к узлу связного списка по индексу index */
function access(head: ListNode | null, index: number): ListNode | null {
    for (let i = 0; i < index; i++) {
        if (!head) {
            return null;
        }
        head = head.next;
    }
    return head;
}

/* Доступ к узлу связного списка по индексу index */
ListNode? access(ListNode? head, int index) {
  for (var i = 0; i < index; i++) {
    if (head == null) return null;
    head = head.next;
  }
  return head;
}

/* Доступ к узлу связного списка по индексу index */
pub fn access<T>(head: Rc<RefCell<ListNode<T>>>, index: i32) -> Option<Rc<RefCell<ListNode<T>>>> {
    fn dfs<T>(
        head: Option<&Rc<RefCell<ListNode<T>>>>,
        index: i32,
    ) -> Option<Rc<RefCell<ListNode<T>>>> {
        if index <= 0 {
            return head.cloned();
        }

        if let Some(node) = head {
            dfs(node.borrow().next.as_ref(), index - 1)
        } else {
            None
        }
    }

    dfs(Some(head).as_ref(), index)
}

/* Доступ к узлу связного списка по индексу index */
ListNode *access(ListNode *head, int index) {
    for (int i = 0; i < index; i++) {
        if (head == NULL)
            return NULL;
        head = head->next;
    }
    return head;
}

/* Доступ к узлу связного списка по индексу index */
fun access(head: ListNode?, index: Int): ListNode? {
    var h = head
    for (i in 0..<index) {
        if (h == null)
            return null
        h = h.next
    }
    return h
}

### Доступ к узлу связного списка по индексу index ###
def access(head, index)
  for i in 0...index
    return nil if head.nil?
    head = head.next
  end

  head
end

def find(head: ListNode, target: int) -> int:
    """Найти в связном списке первый узел со значением target"""
    index = 0
    while head:
        if head.val == target:
            return index
        head = head.next
        index += 1
    return -1

/* Найти в связном списке первый узел со значением target */
int find(ListNode *head, int target) {
    int index = 0;
    while (head != nullptr) {
        if (head->val == target)
            return index;
        head = head->next;
        index++;
    }
    return -1;
}

/* Найти в связном списке первый узел со значением target */
int find(ListNode head, int target) {
    int index = 0;
    while (head != null) {
        if (head.val == target)
            return index;
        head = head.next;
        index++;
    }
    return -1;
}

/* Найти в связном списке первый узел со значением target */
int Find(ListNode? head, int target) {
    int index = 0;
    while (head != null) {
        if (head.val == target)
            return index;
        head = head.next;
        index++;
    }
    return -1;
}

/* Найти в связном списке первый узел со значением target */
func findNode(head *ListNode, target int) int {
    index := 0
    for head != nil {
        if head.Val == target {
            return index
        }
        head = head.Next
        index++
    }
    return -1
}

/* Найти в связном списке первый узел со значением target */
func find(head: ListNode, target: Int) -> Int {
    var head: ListNode? = head
    var index = 0
    while head != nil {
        if head?.val == target {
            return index
        }
        head = head?.next
        index += 1
    }
    return -1
}

/* Найти в связном списке первый узел со значением target */
function find(head, target) {
    let index = 0;
    while (head !== null) {
        if (head.val === target) {
            return index;
        }
        head = head.next;
        index += 1;
    }
    return -1;
}

/* Найти в связном списке первый узел со значением target */
function find(head: ListNode | null, target: number): number {
    let index = 0;
    while (head !== null) {
        if (head.val === target) {
            return index;
        }
        head = head.next;
        index += 1;
    }
    return -1;
}

/* Найти в связном списке первый узел со значением target */
int find(ListNode? head, int target) {
  int index = 0;
  while (head != null) {
    if (head.val == target) {
      return index;
    }
    head = head.next;
    index++;
  }
  return -1;
}

/* Найти в связном списке первый узел со значением target */
pub fn find<T: PartialEq>(head: Rc<RefCell<ListNode<T>>>, target: T) -> i32 {
    fn find<T: PartialEq>(head: Option<&Rc<RefCell<ListNode<T>>>>, target: T, idx: i32) -> i32 {
        if let Some(node) = head {
            if node.borrow().val == target {
                return idx;
            }
            return find(node.borrow().next.as_ref(), target, idx + 1);
        } else {
            -1
        }
    }

    find(Some(head).as_ref(), target, 0)
}

/* Найти в связном списке первый узел со значением target */
int find(ListNode *head, int target) {
    int index = 0;
    while (head) {
        if (head->val == target)
            return index;
        head = head->next;
        index++;
    }
    return -1;
}

/* Найти в связном списке первый узел со значением target */
fun find(head: ListNode?, target: Int): Int {
    var index = 0
    var h = head
    while (h != null) {
        if (h._val == target)
            return index
        h = h.next
        index++
    }
    return -1
}

### Поиск первого узла со значением target в связном списке ###
def find(head, target)
  index = 0
  while head
    return index if head.val == target
    head = head.next
    index += 1
  end

  -1
end

class ListNode:
    """Класс узла двусвязного списка"""
    def __init__(self, val: int):
        self.val: int = val                # Значение узла
        self.next: ListNode | None = None  # Ссылка на следующий узел
        self.prev: ListNode | None = None  # Ссылка на предыдущий узел

/* Структура узла двусвязного списка */
struct ListNode {
    int val;         // Значение узла
    ListNode *next;  // Указатель на следующий узел
    ListNode *prev;  // Указатель на предыдущий узел
    ListNode(int x) : val(x), next(nullptr), prev(nullptr) {}  // Конструктор
};

/* Класс узла двусвязного списка */
class ListNode {
    int val;        // Значение узла
    ListNode next;  // Ссылка на следующий узел
    ListNode prev;  // Ссылка на предыдущий узел
    ListNode(int x) { val = x; }  // Конструктор
}

/* Класс узла двусвязного списка */
class ListNode(int x) {  // Конструктор
    int val = x;    // Значение узла
    ListNode next;  // Ссылка на следующий узел
    ListNode prev;  // Ссылка на предыдущий узел
}

/* Структура узла двусвязного списка */
type DoublyListNode struct {
    Val  int             // Значение узла
    Next *DoublyListNode // Указатель на следующий узел
    Prev *DoublyListNode // Указатель на предыдущий узел
}

// NewDoublyListNode Инициализация
func NewDoublyListNode(val int) *DoublyListNode {
    return &DoublyListNode{
        Val:  val,
        Next: nil,
        Prev: nil,
    }
}

/* Класс узла двусвязного списка */
class ListNode {
    var val: Int // Значение узла
    var next: ListNode? // Ссылка на следующий узел
    var prev: ListNode? // Ссылка на предыдущий узел

    init(x: Int) { // Конструктор
        val = x
    }
}

/* Класс узла двусвязного списка */
class ListNode {
    constructor(val, next, prev) {
        this.val = val  ===  undefined ? 0 : val;        // Значение узла
        this.next = next  ===  undefined ? null : next;  // Ссылка на следующий узел
        this.prev = prev  ===  undefined ? null : prev;  // Ссылка на предыдущий узел
    }
}

/* Класс узла двусвязного списка */
class ListNode {
    val: number;
    next: ListNode | null;
    prev: ListNode | null;
    constructor(val?: number, next?: ListNode | null, prev?: ListNode | null) {
        this.val = val  ===  undefined ? 0 : val;        // Значение узла
        this.next = next  ===  undefined ? null : next;  // Ссылка на следующий узел
        this.prev = prev  ===  undefined ? null : prev;  // Ссылка на предыдущий узел
    }
}

/* Класс узла двусвязного списка */
class ListNode {
    int val;        // Значение узла
    ListNode? next;  // Ссылка на следующий узел
    ListNode? prev;  // Ссылка на предыдущий узел
    ListNode(this.val, [this.next, this.prev]);  // Конструктор
}

use std::rc::Rc;
use std::cell::RefCell;

/* Тип узла двусвязного списка */
#[derive(Debug)]
struct ListNode {
    val: i32, // Значение узла
    next: Option<Rc<RefCell<ListNode>>>, // Указатель на следующий узел
    prev: Option<Rc<RefCell<ListNode>>>, // Указатель на предыдущий узел
}

/* Конструктор */
impl ListNode {
    fn new(val: i32) -> Self {
        ListNode {
            val,
            next: None,
            prev: None,
        }
    }
}

/* Структура узла двусвязного списка */
typedef struct ListNode {
    int val;               // Значение узла
    struct ListNode *next; // Указатель на следующий узел
    struct ListNode *prev; // Указатель на предыдущий узел
} ListNode;

/* Конструктор */
ListNode *newListNode(int val) {
    ListNode *node;
    node = (ListNode *) malloc(sizeof(ListNode));
    node->val = val;
    node->next = NULL;
    node->prev = NULL;
    return node;
}

/* Класс узла двусвязного списка */
// Конструктор
class ListNode(x: Int) {
    val _val: Int = x           // Значение узла
    val next: ListNode? = null  // Ссылка на следующий узел
    val prev: ListNode? = null  // Ссылка на предыдущий узел
}

# Класс узла двусвязного списка
class ListNode
  attr_accessor :val    # Значение узла
  attr_accessor :next   # Ссылка на следующий узел
  attr_accessor :prev   # Ссылка на предыдущий узел

  def initialize(val=0, next_node=nil, prev_node=nil)
    @val = val
    @next = next_node
    @prev = prev_node
  end
end