Объяснение о фиктивных узлах и указателях в связанных списках

Question

У меня есть следующий класс для узла списка:

    def __init__(self, x):
        self.val = x
        self.next = None

Если я инициализирую списки l и r следующим образом:

l = ListNode(1)
l.next = ListNode(4)
l.next.next = ListNode(5)

r = ListNode(1)
r.next = ListNode(3)
r.next.next = ListNode(4)

# l: 1->4->5
# r: 1->3->4

и фиктивная /текущие узлы как

dummy = cur = ListNode(0)
# cur = 0
# dummy = 0

, когда я устанавливаю

cur.next = l
# cur = 0->1->4->5
# dummy = 0->1->4->5

, оба списка помещают l во позицию второго узла, но когда я устанавливаю только

cur = cur.next
# cur = 1->4->5
# dummy = 0->1->4->5

список cur теряет первый узел. И затем, когда я устанавливаю

cur.next = r
# cur = 1->1->3->4
# dummy = 0->1->1->3->4

, список cur присоединяет список r ко второй позиции, а список dummy прикрепляет его к третьей позиции. Я думаю, что dummy будет выглядеть как 0->1->3->4

Я полагаю, что это то, чего мне не хватает ни в указателях в python, ни в связанных списках вообще. Любое объяснение будет оценено!

Answer 1

Важным моментом здесь является то, что когда вы устанавливаете переменную Python для объекта, это указатель, а не значение. Таким образом, в этом коде здесь:

dummy = cur = ListNode(0)
# cur = 0
# dummy = 0

dummy и cur оба указывают на один и тот же объект (то есть на один и тот же одноэлементный список). Когда вы добавляете другой список к cur, вы одновременно добавляете его к dummy, потому что это тот же список.

Когда вы делаете это:

cur = cur.next
# cur = 1->4->5
# dummy = 0->1->4->5

выне создавая новый список, вы просто перемещаете указатель cur по существующему списку. Оба указателя являются частью одного и того же списка, но dummy указывает на первый элемент, а cur указывает на второй элемент.

Каждый раз, когда вы вызываете ListNode(), вы создаете новый узел, поэтомуесли вы хотите создать два узла с одинаковым значением, вам нужно вызвать инициализатор дважды:

dummy = ListNode(0)
cur = ListNode(0)
# cur and dummy both have values of 0, but they're different list objects!

---

Кроме того: я не уверен, что это то, что вы получили, когда упомянули«фиктивные узлы», но обратите внимание, что нет особой необходимости в специальном «фиктивном узле» в вашем списке, чтобы обозначить конец списка;None отлично подходит для этой цели (т. Е. Конец списка - это тот, чей next is None).