我正在尝试解决算法专家上的以下问题：
移位链表
编写一个函数，该函数接收单向链表的头部和一个整数
k，将列表移动到位(即，不会创建一个全新的 列表)k位置，并返回其新头部。移动链表意味着向前或向后移动其节点并换行 在适当的情况下，它们在列表周围。例如，移动链表 向前移动一个位置将使它的尾巴成为链接的新头部 列表。
节点是向前移动还是向后移动取决于是否
k是正面的还是负面的。每个
LinkedList节点都有一个整数value以及next指向列表中下一个节点或None/null它是否是列表的尾部。您可以假设输入链表将始终至少有一个节点; 换句话说，头部永远不会
None/null.示例输入
head = 0 -> 1 -> 2 -> 3 -> 4 -> 5 // the head node with value 0 k = 2示例输出
4 -> 5 -> 0 -> 1 -> 2 -> 3 // the new head node with value 4
问题为代码提供的大纲如下：
class LinkedList: def __init__(self, value): self.value = value self.next = None def shiftLinkedList(head, k): #Write your code here. pass
我想我在链表上的背景非常有限，因为从我在链表上读到的每个资源来看，它的总体大纲都需要节点类，并具有在LinkedList类内旋转或移动的所有方法。
我假设函数的 head 参数将是一个表示列表位置的整数，但我如何将 head 引用回原始列表？我已经在我的 Thonny 编辑器中编写了代码，但我在LinkedList类中编写了函数，并在列出列表后简单地调用了它。
例如：
class Node:
def __init__self(data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def push(self, newhead):
newnode = Node(new_data)
newnode.next = self.head
self.head = newnode
list1 = LinkedList()
list1.head = Node(1)
e2 = 2
e3 = 3
list1.head.next = e2
e2.next = e3
只有在我建立了链表后，我才能在类内创建一个方法来移动或旋转它。还是我错了？
我尝试按照算法想要的方式创建一个函数，但我仍然卡住了。我想我真正困惑的是参数head是整数还是LinkedList？
这是我的完整尝试：
class Node:
def __init__(self, data):
self.data = data #assign data
self.next = None #initialize next as null
class LinkedList:
#function to initalize the linked list object
def __init__(self):
self.head = None
def printList(self):
temp = self.head
while(temp):
print(temp.data)
temp = temp.next
def moveToFront(self):
tmp = self.head
sec_last = None
if not tmp or not tmp.next:
return
while tmp and tmp.next:
sec_last = tmp
tmp = tmp.next
sec_last.next = None
tmp.next = self.head
self.head = tmp
def shiftList(head, k):
if not head:
return
tmp = head
length = 1
while(temp.next != None):
tmp = tmp.next
length += 1
if(k>length):
k = k%length
k = length - k
if(k==0 or k==length):
return head
current = head
cmt = 1
while(cmt < k and current != None):
current = current.next
cmt += 1
if(current==None):
return head
kthnode = current
tmp.next = head
head = kthnode.next
kthnode.next = None
return head
我假设函数的 head 参数将是一个表示列表位置的整数
不，列表的头部是LinkedList实例。因此head.value是列表中第一个节点的值，head.next是对列表中第二个节点的引用。
在您的尝试中，您已经从原始更改了LinkedList的定义，并创建了另一个类，称为Node，这确实是LinkedList应该是什么(除了您称属性为data而不是value)。这样做是可以理解的，因为您希望为整个链表提供一种容器类，并为该列表中的单个节点保留一个单独的类Node。但是此代码质询不适用于此类容器类。
它只适用于一个表示节点的类，但通过其next成员，从中推断出整个列表。此外，他们希望函数在移位完成后返回对已成为列表头部的节点的引用。这是一种与容器类不同的工作方式，在容器类中，您将改变head成员，并且不会返回任何内容：调用方只需通过修改后的head成员访问列表。
因此，您打算执行的操作本质上并没有错误，只是不是此代码挑战正在使用的数据结构。你应该随它去。
我真正困惑的是参数"head"是整数还是链接列表
它是一个节点，但列表是从中推断出来的。他们称他们的班级为LinkedList而不是Node，这可能会有点令人困惑，但这是你如何看待它的问题。
因此，这是您可以解决它的方法：
- 首先找出列表中的最后一个节点是什么。为此，您必须从头部开始(您没有其他东西)并逐步浏览列表，直到您碰到它的末尾。还要维护一个计数器，以便最后您知道列表中有多少个节点。
- 然后创建一个从该尾节点到头节点的链接，以便列表现在变为循环：它不再有尽头
- 找出哪个节点在此循环列表中比尾节点早k 步。由于不可能在列表中向后走，因此您实际上应该向前走 size-k 步，因此您需要在第一步中确定的列表大小。 找到的节点
- 之后的节点应成为头节点。
- 使该节点本身成为新的尾节点：断开它与它之后的节点(新头)的链接。
- 返回新的头部引用
应该做另一件事来保护此代码免受k的巨大值的影响。假设列表有 6 个元素，k是 600，那么当然在循环列表中运行 600 次是没有意义的，因为我们可以预测您将在开始的地方结束！600 是 6 的倍数...因此，为了提高效率，您需要将k减少到小于列表大小的数字。知道您需要向前走多少步的公式是-k % size.
以下是这个想法的实现：
def shiftLinkedList(head, k):
if not head:
return # Nothing to do
# Determine size of the list, and its tail node
size = 1
tail = head
while tail.next:
size += 1
tail = tail.next
# Temporarily make the list cyclic
tail.next = head
# Find out where to cut the cycle
for _ in range(-k % size):
tail = tail.next
head = tail.next
# Cut the cycle
tail.next = None
return head