Обмен между двумя узлами с использованием заданных элементов, которые присутствуют в этих узлах.Python-3.0 используется для написания кода

Question

Я написал код, но я думаю, что функция push не работает, так как при вызове функции display в связанном списке не отображается ни один элемент.Пожалуйста, скажите мне, как добавить элементы в связанный список и объяснить шаги.Я думаю, что last_pointer рассматривается как локальная переменная, и он не хранит ее последнее значение.Если каждый раз я объявляю last_pointer, он не будет добавлен к следующему узлу.

Вывод:

Linked list before any swapping
key1 is not present in the list
key1 is not present in the list
key1 is not present in the list
____________________

---

# Swapping between two nodes present in linkedlist

class node:
    def __init__(self,data):
        self.data=data
        self.next=None
class linkedlist:
    def __init__(self):
        self.head=None
    def push(self,newdata):
        newnode=node(newdata)
        if(self.head==None):
            last_pointer=self.head
            last_pointer=newnode
            last_pointer=last_pointer.next
        else:
            last_pointer.next=newnode
            last_pointer=last_pointer.next
    def swapnodes(self,key1,key2):
        node1=self.head
        node2=self.head
        #if elements are similar
        if(key1==key2):
            print("keys are similar")
            return
        #find previous of element and element location in the list
        while(node1):
            if(node1==key1):
                break
            prevofnode1=node1
            node1=node1.next
        while(node2):
            if(node2==key2):
                break
            prevofnode2=node2
            node2=node2.next
        #if elements are not present in the list
        if(node1==None):
            print("key1 is not present in the list")
            return
        if(node2==None):
            print("key2 is not present in the list")
            return
        #if node present at beginning or at mid or at end
        temp1=node2.next
        temp2=node1.next
        if(prevofnode1==None):
            self.head=node2
            node2.next=node1.next
            prevofnode2=node1
            node1.next=temp1
            temp1=None
        else:
            prevofnode1=node2
            node2.next=node1.next
            prevofnode2=node1
            node1.next=temp1
            temp1=None
        if(prevofnode2==None):
            self.head=node1
            node1.next=node2.next
            prevofnode1=node2
            node2.next=temp2
            temp2=None
        else:
            prevofnode2=node1
            node1.next=node2.next
            prevofnode1=node2
            node2.next=temp2
            temp2=None
    def display(self):
        temp=self.head
        while(temp):
            print(temp.data)
            temp=temp.next
llist=linkedlist()
llist.push(22)
llist.push(92)
llist.push(-20)
llist.push(2)
llist.push(23)
llist.push(102)
print("Linked list before any swapping")
llist.display()
llist.swapnodes(22,102)
llist.swapnodes(22,-20)
llist.swapnodes(22,13)
llist.display()

Answer 1

Я переписал код, чтобы быть более кратким. Чтобы добавить элементы в связанный список, необходимо рассмотреть два случая:

• Связанный список пуст или
• Связанный список имеет хотя бы один узел

def push(self, newdata):
    if not self.head:
        self.head = Node(newdata)
        self.cur = self.head
    else:
        self.cur.next = Node(newdata)
        self.cur = self.cur.next

Для случая, когда он пуст, мы можем проверить, пусто ли оно, используя if not self.head. Если он пуст, мы назначаем голову новому узлу. Кроме того, мы отслеживаем текущий узел с помощью self.cur. Таким образом, у нас всегда есть указатель на последний узел, и нам не нужно будет перебирать, когда мы добавляем больше значений. Теперь для случая, когда в связанном списке уже есть элементы, мы устанавливаем указатель next текущего узла на новый узел. В обоих случаях мы должны переместить указатель на следующий узел.

Чтобы поменять местами узлы с двумя значениями, это немного сложнее. Есть 4 случая, которые необходимо обработать:

• x и y могут быть или не быть смежными
• x или y может быть головным узлом
• x или y может быть последним узлом
• x и / или y могут отсутствовать в связанном списке

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

# Swapping between two nodes present in linkedlist

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

class Linkedlist:
    def __init__(self):
        self.head = None

    def push(self, newdata):
        if not self.head:
            self.head = Node(newdata)
            self.cur = self.head
        else:
            self.cur.next = Node(newdata)
            self.cur = self.cur.next

    def swap_nodes(self, x, y):
        # Don't swap if same
        if x == y:
            return

        # Search for x (keep track of prev_x and CurrX)
        prev_x = None
        cur_x = self.head
        while cur_x != None and cur_x.data != x:
            prev_x = cur_x
            cur_x = cur_x.next

        # Search for y (keep track of prev_y and cur_y)
        prev_y = None
        cur_y = self.head
        while cur_y != None and cur_y.data != y:
            prev_y = cur_y
            cur_y = cur_y.next

        # If either x or y is not present, nothing to do
        if cur_x == None or cur_y == None:
            return
        # If x is not head of linked list
        if prev_x != None:
            prev_x.next = cur_y
        else: #make y the new head
            self.head = cur_y

        # If y is not head of linked list
        if prev_y != None:
            prev_y.next = cur_x
        else: # make x the new head
            self.head = cur_x

        # Swap next pointers
        temp = cur_x.next
        cur_x.next = cur_y.next
        cur_y.next = temp

    def display(self):
        temp = self.head
        while temp:
            print(temp.data)
            temp = temp.next

llist = Linkedlist()
llist.push(22)
llist.push(92)
llist.push(-20)
llist.push(2)
llist.push(23)
llist.push(102)
llist.display()
print('Linked list before any swapping')
llist.swap_nodes(22,102)
llist.swap_nodes(22,-20)
llist.swap_nodes(22,13)
print(' ')
llist.display()

выход

22
92
-20
2
23
102
Linked list before any swapping

102
92
22
2
23
-20