AlgoVerse

برعکس کردن لیست پیوندی

جهت همه‌ی پیوندهای لیست را با سه اشاره‌گر prev، cur و nxt یکی‌یکی برمی‌گرداند؛ در یک گذر و بدون حافظه‌ی اضافه.

لیست را از اول پیمایش می‌کنیم و پیوند هر گره را به گره‌ی قبلی برمی‌گردانیم. سه اشاره‌گر لازم است:

ادامه‌ی توضیح ↓
ورودی:
n=5خروجی PDF

۱ → ۲ → ۳ → ۴ → ۵ برعکس می‌شود: ۵ → ۴ → ۳ → ۲ → ۱.

  1. class Node:
  2. def __init__(self, val):
  3. self.val = val
  4. self.next = None
  7. def reverse_list(items):
  8. head = None
  9. for x in reversed(items):
  10. node = Node(x)
  11. node.next = head
  12. head = node
  13. # prev: the part already reversed; cur: the part still to do.
  14. prev, cur = None, head
  15. while cur is not None:
  16. nxt = cur.next
  17. cur.next = prev
  18. prev = cur
  19. cur = nxt
  20. head = prev
  21. out = []
  22. while head is not None:
  23. out.append(head.val)
  24. head = head.next
  25. return out

ناوردا: prev همیشه سر بخش برعکس‌شده است و cur سر بخش باقی‌مانده؛ هیچ گره‌ای گم نمی‌شود چون nxt قبل از برگرداندن پیوند ذخیره می‌شود.

شروع اجرا

prevتهی
curتهی

متغیرهای محلی

نارنجی = در همین گام عوض شد

items list

12345

Call stack

  1. reverse_list()خط 7
گام ۱ از ۸۴
خط سیاه = flip · خط نارنجی = گام کلیدیbuilt: 0/1 · flip: 0/5 · advance: 0/5 · done: 0/1
    توضیح

    ایده

    لیست را از اول پیمایش می‌کنیم و پیوند هر گره را به گره‌ی قبلی برمی‌گردانیم. سه اشاره‌گر لازم است:

    • prev: سر بخشی که تا اینجا برعکس شده،
    • cur: گره‌ای که الان پیوندش برمی‌گردد،
    • nxt: گره‌ی بعدی، که باید قبل از برگرداندن پیوند ذخیره شود، وگرنه بقیه‌ی لیست گم می‌شود.

    در پایان prev سر لیست برعکس‌شده است.

    هزینه

    یک گذر و چند اشاره‌گر: زمان O(n) و حافظه‌ی O(1). هیچ گره‌ای کپی یا جابه‌جا نمی‌شود.

    در trace به چه چیزی نگاه کنی

    • دو لیست کشیده شده: از prev (بخش برعکس‌شده) و از cur (بخش باقی‌مانده)؛ با هر گام یک گره از دومی به اولی می‌رود.