我已经编写了代码,但我认为push函数不起作用,因为当我调用display function时,链接列表中没有元素显示。请告诉我如何在链表中追加元素并解释步骤。我认为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()
我重写了代码更简洁。要在链表中追加元素,您需要考虑两种情况:
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,同时保持跟踪其先前和当前指针。如果其中一个不存在,我们返回。
# 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