用while循环交换单链表中的节点

Question

我正在尝试交换单链列表中的节点对，这样，如果链列表为1-> 2-> 3-> 4，那么将输出的是2-> 1-> 4-> 3 。我已经设法输出通过交换第一对来实现2-> 1-> 3-> 4，但是现在我不确定如何遍历整个列表并执行其余的交换。我的直觉告诉我，我需要使用while循环，但是我不确定如何实现这一点。有人可以帮忙吗？

class Node():
    def __init__(self,dataval=None):
        self.dataval=dataval
        self.nextval=None

class Linkedlist():
    def __init__(self,headval=None):
        self.headval=headval

    def printlist(self):
        headval=self.headval
        while headval is not None:
            print(headval.dataval)
            headval=headval.nextval

    def swapnodes(self,headval):
        temp=headval.nextval
        headval.nextval=temp.nextval
        temp.nextval=headval
        self.headval=temp


List1=Linkedlist()
Node1=Node("1")
Node2=Node("2")
Node3=Node("3")
Node4=Node("4")
List1.headval=Node1
Node1.nextval=Node2
Node2.nextval=Node3
Node3.nextval=Node4
List1.swapnodes(Node1)
List1.printlist()

Answer 1

进行成对交换时，您需要跟踪三个不同的节点。您需要当前正在交换的两个节点以及该对之前的节点。您当前的函数swapnodes()使用headval和temp来跟踪正在交换的两个链表节点，这些节点足以进行第一次交换。但是，当您尝试交换Node3和Node4时，仍然需要引用Node1，即在交换当前对之前的节点才能将Node1.next设置为Node4。您是正确的，您将需要某种while循环来完成此操作。使用虚拟头节点也将有助于推广该算法。

1. 初始化dummyHead（dummyHead.next =头）
2. 将prevNode设置为dummyHead
3. 将currNode设置为head
4. 使用while循环迭代链接列表：交换一对节点，更新prevNode，更新currNode
5. 返回dummyHeader.next