如何在Python中交换单链表节点？

Question

目前，我正在尝试根据我的主函数 switch(myList,index) 来重新排列一个链表。

def createList(plist):
    linkedList = None
    # goes backwards, adding each element to the beginning
    # of the list.  
    for index in range(len(plist)-1, -1, -1):
        linkedList = insertValueHead(linkedList, plist[index])
    return linkedList

def insertValueHead(linkedList, value):
    newnode = {}
    newnode["data"] = value
    #set the next pointer of this new node to the head of the list, linkedList
    #newnode is now the head of the list 
    newnode["next"] = linkedList
    return newnode

def listString(linkedList):
   ptr = linkedList
   str1 = ''
   while ptr != None:
     str1 += str(ptr['data'])
     ptr = ptr['next']
     if ptr != None:
      str1 += "->"
  str1 = str1
  return str1

def switch(j, i):
   head = j
   currentItem = j[0]     # The head again
   prevItem = 1       # The item that links to tempItem
   for x in range(i):    # Find the item to swap
        prevItem = currentItem
        currentItem = currentItem['next']
        currentItem = currentItem['next']
        temp = currentItem['next']
        currentItem['next'] = head['next']
        head['next'] = prevItem['next']
        prevItem['next'] = temp

def testSwitch():
    #test code to ensure that switch() is working correctly.
    myList = createList([10, 20, 30, 40, 50, 60])
    print "The initial list", listString(myList)
    myList = switch(myList, 2)
    print "Switching the 1 and the 2.  Resulting list is ", listString(myList)

testSwitch()

这样应该能得到一个元素交换后的列表。但是，当我运行它时，输出是这样的：

The initial list 10->20->30->40->50->60
Switching the 1 and the 2.  Resulting list is 

接下来出现了这个错误：

    currentItem = currentItem['next']
TypeError: list indices must be integers, not str

我到底哪里出错了？我似乎搞不清楚……

Answer 1

你的缩进不正确，这就是你遇到问题的原因。

def switch(j, i):
    head = j
    currentItem = j[0]     # The head again
    prevItem = 1       # The item that links to tempItem
    for x in range(i):    # Find the item to swap
        prevItem = currentItem
        currentItem = currentItem['next']
        currentItem = currentItem['next']
        temp = currentItem['next']
        currentItem['next'] = head['next']
        head['next'] = prevItem['next']
        prevItem['next'] = temp

在一个函数或循环里面，要缩进四个空格。你不能把 j[0] 赋值给当前项，因为它是一个字典。

Answer 2

单向链表在需要支持切换操作时并不是一个很实用的结构。如果使用双向链表，节点可以同时指向前后，这样就很简单了；但如果是单向链表，你至少得遍历一遍链表才能找到需要的节点。而且，你的代码看起来很乱，别人根本没法调试。因此，

• 建议使用基于类的列表，而不是直接使用节点子类的项。
• 如果你需要进行切换操作，真的应该使用双向链表。可以考虑使用Linux的链表约定，链表的两端也可以是一个列表节点。

类似于

 class Node(object):
     prev = None
     next = None

 class List(object):
     def __init__(self):
         self.head = self
         self.tail = self
         self.prev = self
         self.next = self
         self.nil = self

     def insert_head(self, node):
         node.next = self.head.next
         self.head.next.prev = node
         node.prev = self.head
         self.head.next = node

     def __iter__(self):
         current = self.head.next
         while current != self.nil:
             yield current
             current = current.next

     def __str__(self):  # the "list_string" op
         items = []
         return ' -> '.join(map(str, self))

 class TestNode(Node):
     def __init__(self, value):
         self.value = value

     def __repr__(self):
         return repr(self.value)

list = List()
list.insert_head(TestNode('a'))
list.insert_head(TestNode('b'))
print(list)