Əlaqəli siyahı məsələlərinin çoxu bir neçə texnikaya əsaslanır: göstəricilərin (next) yenidən qurulması, iki göstərici (yavaş/sürətli və ya aralı) və saxta baş (dummy head). Burada Node və siyahı reallaşdırması əvvəlki mövzudan tanışdır: Node(value, next).

Siyahının çevrilməsi: hər addımda bir keçid əks istiqamətə dönür
Siyahının çevrilməsi: hər addımda bir keçid əks istiqamətə dönür

Köməkçi funksiyalar

Testlər üçün siyahını massivdən qurmaq və geri massivə çevirmək rahatdır.

python
class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

def build(items):
    head = None
    for v in reversed(items):
        head = Node(v, head)
    return head

def to_list(head):
    out = []
    while head:
        out.append(head.value)
        head = head.next
    return out

print(to_list(build([1, 2, 3])))
text
[1, 2, 3]

Siyahının çevrilməsi

Üç göstərici saxlayırıq: prev (artıq çevrilmiş hissənin başı), head (cari düyün) və nxt (hələ itirilməməli növbəti düyün). Hər addımda head.next-i prev-ə yönəldirik. Vaxt O(n), əlavə yaddaş O(1).

python
def reverse(head):
    prev = None
    while head:
        nxt = head.next
        head.next = prev
        prev = head
        head = nxt
    return prev

print(to_list(reverse(build([1, 2, 3, 4]))))
print(to_list(reverse(None)))
text
[4, 3, 2, 1]
[]

💡 nxt = head.next sətri head.next = prev-dən əvvəl yazılmalıdır, əks halda siyahının qalan hissəsi itir.

Orta düyün: yavaş və sürətli göstərici