我目前正在解决问题。
If linked list is 1,2,3,4,5 and k=2 then output should be 4,5,1,2,3
我的方法是为最后一个节点和倒数第二个节点创建一个双指针。到达最后一个节点后，将其连接到头的旁边，并使倒数第二个指针为零。继续此过程，直到k值。
例外输入和输出为
class node:
def __init__ (self,data):
self.data = data
self.next = None
class linkedlist:
def __init__(self):
self.head = None
self.tail = None
def addlast(self,data):
a = node(data)
if self.head == None:
self.head = a
self.tail = a
else:
self.tail.next = a
self.tail = a
def printlist(self):
current = self.head
while (current != None):
print(current.data,"-->",end="")
current = current.next
print("NUll")
def rotatelist(self):
k = 2
while k:
current = self.head.next
previous = self.head
while(current.next):
current = current.next
previous = previous.next
current.next = self.head
self.head= current
previous = None
obj = linkedlist()
obj.addlast(1)
obj.addlast(2)
obj.addlast(3)
obj.addlast(4)
obj.addlast(5)
obj.rotatelist()
obj.printlist()
有四个问题：
-
循环永远不会结束，因为
k不适用。在范围上循环更像蟒蛇 -
将
previous设置为None并不能满足您的要求。应将previous.next设置为None -
该函数不更新
self.tail，但它应该更新。 -
当列表中的元素少于2个时，将出现错误，然后代码将进行无效引用。您可以捕获这种情况，并只返回不变的列表，因为轮换对少于2个元素的列表没有影响。
那么，在该函数中对k的值进行硬编码不是很方便用户。它最好是一个调用方可以为其传递值的参数：
def rotatelist(self, k): # k should be parameter
if self.head == self.tail: # Fewer than 2 elements
return
for _ in range(k): # Determine the number of iterations
current = self.head.next
previous = self.head
while current.next:
current = current.next
previous = previous.next
current.next = self.head
self.head= current
previous.next = None # Correction
self.tail = previous # Update tail
obj = linkedlist()
obj.addlast(1)
obj.addlast(2)
obj.addlast(3)
obj.addlast(4)
obj.addlast(5)
obj.rotatelist(2) # Pass the value of k
obj.printlist()
但是这种方法仍然不有效。它需要为每个循环迭代整个列表。此外，如果k比列表的大小大得多，则会浪费大量时间来完全旋转列表，使其再次回到初始状态，然后继续。
为了提高效率，请使用k %= n(其中n是列表的大小(。暂时使列表循环，然后向前移动tail引用n-k步，对齐head，最后再次打破循环：
def size(self):
size = 0
current = self.head
while current:
size += 1
current = current.next
return size
def rotatelist(self, k):
if self.head == self.tail:
return
# Limit k to avoid useless iterations
n = self.size()
k %= n
# Make list circular
self.tail.next = self.head
# Move tail
for _ in range(n - k): # Determine the number of iterations
self.tail = self.tail.next
# Align head with tail
self.head = self.tail.next
# Break circle
self.tail.next = None
试试我的解决方案。
class node:
def __init__ (self,data):
self.data = data
self.next = None
class linkedlist:
def __init__(self):
self.head = None
self.tail = None
def addlast(self,data):
if (self.head==None):
self.head = self.tail = node(data)
else:
a = node(data)
self.tail.next = a
self.tail = a
def printlist(self):
current = self.head
while (current != None):
print(current.data,"-->",end="")
current = current.next
print("NUll")
def rotatelist(self):
k = 2
while k:
current = self.head.next
previous = self.head
while(current.next):
current = current.next
previous = previous.next
current.next = self.head
self.head= current
previous.next = None
k-=1
if k<=0:
break
obj = linkedlist()
obj.addlast(1)
obj.addlast(2)
obj.addlast(3)
obj.addlast(4)
obj.addlast(5)
obj.rotatelist()
obj.printlist()