如何在Python中与linkedlist类外部的linkedlist头交互？

Question

我试图解决以下问题algo专家级：

编写一个函数，该函数接收一个单向链接列表的头部和一个整数k，按k位置移动列表（即，不创建一个全新的列表），并返回其新头部。

移动链接列表意味着向前或向后移动其节点，并在适当的情况下将其环绕在列表中。例如，将链表向前移动一个位置将使其尾部成为链表的新头部。

节点向前还是向后移动取决于k是正还是负。

每个LinkedList节点都有一个整数值，还有一个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 

只有建立了链表后，才能在类中创建一个方法来移动或旋转它。还是我错了？

我试图按照algo想要的方式创建一个函数，但我仍然卡住了。我想我真正困惑的是参数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

Answer 1

我假设函数的head参数是一个整数，表示列表的位置

不，列表的头部是LinkedList实例。所以head.value是列表中第一个节点的值，head.next是对列表中第二个节点的引用。

在您的尝试中，您已经从原来的定义更改了LinkedList的定义，并创建了另一个类，称为Node，这就是LinkedList应该是的（除了您将属性称为data>而不是value）。您这样做是可以理解的，因为您希望为整个链表拥有一种容器类，并为该列表中的单个节点保留一个单独的类Node。但是这个代码挑战不适用于这样的容器类。

它只适用于一个代表节点的类，但是通过它的下一个成员可以推断出整个列表。此外，他们希望函数返回一个引用，该节点在移位完成后成为列表的头部。这是一种不同于容器类的工作方式，在容器类中，您将变异head成员，并且不会返回任何东西：调用者将通过修改后的head成员访问列表。

因此，您想要做的并不是本质上的错误，只是不是这个代码挑战所使用的数据结构。你应该随大流。

我真正困惑的是参数‘head’是整数还是linkedlist

它是一个节点，但列表是从中推断出来的。他们调用自己的类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