Les listes chaînées sont une structure de données fondamentale en informatique. Cet article examine trois techniques clés : la suppression d'éléments, la conception complète d'une liste et l'inversion d'une liste chaînée.

203. Suppression d'éléments dans une liste chaînée

Le but est de retirer tous les nœuds dont la valeur correspond à un paramètre donné. Une approche courante utilise un nœud sentinelle pour simplifier la gestion des cas limites.

class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        sentinel = ListNode()
        sentinel.next = head
        predecessor = sentinel
        while predecessor.next:
            if predecessor.next.val == val:
                predecessor.next = predecessor.next.next
            else:
                predecessor = predecessor.next
        return sentinel.next

707. Conception d'une liste chaînée

Implémenter une liste chaînée avec des opérations d'accès, d'insertion et de suppresion. Voici deux versions : une liste chaînée simple et une liste doublement chaînée.

Liste chaînée simple

class Node:
    def __init__(self, value=0, link=None):
        self.value = value
        self.link = link

class SimpleLinkedList:
    def __init__(self):
        self.anchor = Node()
        self.length = 0

    def access(self, index: int) -> int:
        if index < 0 or index >= self.length:
            return -1
        pointer = self.anchor.link
        for _ in range(index):
            pointer = pointer.link
        return pointer.value

    def prepend(self, value: int) -> None:
        self.anchor.link = Node(value, self.anchor.link)
        self.length += 1

    def append(self, value: int) -> None:
        current = self.anchor
        while current.link:
            current = current.link
        current.link = Node(value)
        self.length += 1

    def insert_at(self, index: int, value: int) -> None:
        if index < 0 or index > self.length:
            return
        current = self.anchor
        for _ in range(index):
            current = current.link
        current.link = Node(value, current.link)
        self.length += 1

    def remove_at(self, index: int) -> None:
        if index < 0 or index >= self.length:
            return
        current = self.anchor
        for _ in range(index):
            current = current.link
        current.link = current.link.link
        self.length -= 1

Liste doublement chaînée

class DoubleNode:
    def __init__(self, value=0, before=None, after=None):
        self.value = value
        self.before = before
        self.after = after

class DoubleLinkedList:
    def __init__(self):
        self.first = None
        self.last = None
        self.count = 0

    def access(self, index: int) -> int:
        if index < 0 or index >= self.count:
            return -1
        if index < self.count // 2:
            node = self.first
            for _ in range(index):
                node = node.after
        else:
            node = self.last
            for _ in range(self.count - index - 1):
                node = node.before
        return node.value

    def prepend(self, value: int) -> None:
        new_node = DoubleNode(value, None, self.first)
        if self.first:
            self.first.before = new_node
        else:
            self.last = new_node
        self.first = new_node
        self.count += 1

    def append(self, value: int) -> None:
        new_node = DoubleNode(value, self.last, None)
        if self.last:
            self.last.after = new_node
        else:
            self.first = new_node
        self.last = new_node
        self.count += 1

    def insert_at(self, index: int, value: int) -> None:
        if index < 0 or index > self.count:
            return
        if index == 0:
            self.prepend(value)
        elif index == self.count:
            self.append(value)
        else:
            if index < self.count // 2:
                current = self.first
                for _ in range(index - 1):
                    current = current.after
            else:
                current = self.last
                for _ in range(self.count - index):
                    current = current.before
            new_node = DoubleNode(value, current, current.after)
            current.after.before = new_node
            current.after = new_node
            self.count += 1

    def remove_at(self, index: int) -> None:
        if index < 0 or index >= self.count:
            return
        if index == 0:
            self.first = self.first.after
            if self.first:
                self.first.before = None
            else:
                self.last = None
        elif index == self.count - 1:
            self.last = self.last.before
            if self.last:
                self.last.after = None
            else:
                self.first = None
        else:
            if index < self.count // 2:
                current = self.first
                for _ in range(index):
                    current = current.after
            else:
                current = self.last
                for _ in range(self.count - index - 1):
                    current = current.before
            current.before.after = current.after
            current.after.before = current.before
        self.count -= 1

206. Inversion d'une liste chaînée

Inverser une liste chaînée en modifient les pointeurs de manière itérative.

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        current_node = head
        reversed_list = None
        while current_node:
            next_ref = current_node.next
            current_node.next = reversed_list
            reversed_list = current_node
            current_node = next_ref
        return reversed_list