在Python的链表中交换对,一个链接消失了吗? [英] Swapping pairs in a linked list in Python, one link disappears?
问题描述
我一直在学习链表,并且在python中实现一个比我预期的要容易.但是,当解决交换链表中的对"问题时,由于某种原因,我的第二个链接在交换过程中消失了.多年来,我一直在盯着这个,并尝试在网上找到的其他解决方案.它们都得到相同的结果,这表明我的问题在于列表本身的实现.或者我在一个看不见的地方犯了一个愚蠢的错误!我将感谢您的新一双眼睛.我做错了什么?
I have been learning about linked lists, and implementing one in python has been easier than I expected. However, when it has come to solving the problem of "swapping pairs in a linked list", for some reason my second link disappears during the swap. I've been staring at this for ages and trying different solutions I found online. They all get the same result which suggests my problem is with the implementation of the list itself. Or I've made a silly error somewhere that I can't see! I would be grateful for a fresh pair of eyes. What have I done wrong?
class Node:
def __init__(self, val):
self.value = val
self.next = None
class LinkedList:
def __init__(self, data):
self.head = Node(data)
def printList(self, head):
while head:
print("->" , head.value)
head = head.next;
def swapPairsR(self, node): # recursive
if node is None or node.next is None:
return node
ptrOne = node
ptrTwo = node.next
nextPtrTwo = ptrTwo.next
# swap the pointers here at at the rec call
ptrTwo.next = node
newNode = ptrTwo
ptrOne.next = self.swapPairsR(nextPtrTwo)
return newNode
def swapPairsI(self, head): # iterative
prev = Node(0)
prev.next = head
temp = prev
while temp.next and temp.next.next:
ptrOne = temp.next
ptrTwo = temp.next.next
# change the pointers to the swapped pointers
temp.next = ptrTwo
ptrOne.next = ptrTwo.next
ptrTwo.next = ptrOne
temp = temp.next.next
return prev.next
thisLList = LinkedList(1)
thisLList.head.next = Node(2)
thisLList.head.next.next = Node(3)
thisLList.head.next.next.next = Node(4)
thisLList.head.next.next.next.next = Node(5)
thisLList.printList(thisLList.head)
print("--------------")
thisLList.swapPairsI(thisLList.head)
thisLList.printList(thisLList.head)
我的输出:
-> 1
-> 2
-> 3
-> 4
-> 5
--------------
-> 1
-> 4
-> 3
-> 5
推荐答案
您的 swapPairsI
函数返回链表的新 head
.您需要相应地更新它:
Your swapPairsI
function is returning the new head
of your linked list.
You need to update it accordingly:
thisLList.head = thisLList.swapPairsI(thisLList.head)
或者更好的是,您应该更改您的 swapPairsI
函数,以使其不必将节点作为参数:
Or better yet, you should change your swapPairsI
function so that it doesn't have to take a node as parameter:
def swapPairsI(self): # iterative
prev = Node(0)
prev.next = self.head
temp = prev
while temp.next and temp.next.next:
ptrOne = temp.next
ptrTwo = temp.next.next
# change the pointers to the swapped pointers
temp.next = ptrTwo
ptrOne.next = ptrTwo.next
ptrTwo.next = ptrOne
temp = temp.next.next
self.head = prev.next
在这种情况下,您可以简单地致电:
In which case, you can simply call:
thisLList.swapPairsI()
这篇关于在Python的链表中交换对,一个链接消失了吗?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!