Обмен узлов в односвязном списке с помощью цикла while - PullRequest
Новая
       15

Обмен узлов в односвязном списке с помощью цикла while

0 голосов
/ 04 апреля 2020

Я пытаюсь поменять пары узлов в односвязном списке так, что если связанный список 1-> 2-> 3-> 4, то будет выведено 2-> 1-> 4-> 3. Мне удалось вывести 2-> 1-> 3-> 4 путем перестановки первой пары, но теперь я не уверен, как l oop по всему списку и выполнить оставшиеся перестановки. Интуиция подсказывает мне, что мне нужно некоторое время использовать l oop, но я не уверен, как это сделать. Может кто-нибудь помочь, пожалуйста? 

class Node():
    def __init__(self,dataval=None):
        self.dataval=dataval
        self.nextval=None

class Linkedlist():
    def __init__(self,headval=None):
        self.headval=headval

    def printlist(self):
        headval=self.headval
        while headval is not None:
            print(headval.dataval)
            headval=headval.nextval

    def swapnodes(self,headval):
        temp=headval.nextval
        headval.nextval=temp.nextval
        temp.nextval=headval
        self.headval=temp


List1=Linkedlist()
Node1=Node("1")
Node2=Node("2")
Node3=Node("3")
Node4=Node("4")
List1.headval=Node1
Node1.nextval=Node2
Node2.nextval=Node3
Node3.nextval=Node4
List1.swapnodes(Node1)
List1.printlist()

1 Ответ

1 голос
/ 04 апреля 2020

Вам нужно будет отслеживать три разных узла при этом парном обмене. Вам нужны два узла, которые в настоящее время меняются местами, а также узел до этой пары. Ваша текущая функция swapnodes() использует headval и temp для отслеживания двух узлов связанного списка, которые меняются местами, что достаточно для первого обмена. Тем не менее, когда вы пытаетесь поменять местами Node3 и Node4, вам все еще нужна ссылка на Node1, узел до замены текущей пары, чтобы иметь возможность установить Node1.next в Node4. Вы правы, что вам понадобится какое-то время, пока я sh выполню это. Использование узла-заглушки также было бы полезно для обобщения этого алгоритма.

  1. Инициализация dummyHead (dummyHead.next = head)
  2. Установите для prevNode значение dummyHead
  3. Установить currNode to head
  4. Используйте пока l oop для итерации связанного списка: поменяйте местами пару узлов, обновите prevNode, обновите currNode
  5. Верните dummyHead.next
...