如何在链表中交换指定索引的节点和头节点？

Question

我现在正在尝试创建一个函数，这个函数可以把链表中指定位置的节点和链表的头节点交换。比如说，如果我的链表（list）里面有这些值 [1, 7, 9, 12]，然后我调用 switch(list, 2)，那么结果应该是 [9, 7, 1, 12]。这是我目前写的代码：

"""
Creates and returns a linked list containing all of the elements
of the Python-style list parameter.  A useful shortcut for testing.
"""
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

'''
Create an empty linked list
'''
def emptyList():
  return None   #absence of a value -- nothing

'''
Creates a string representation of the values in the linked list such as:
5->6->9->14.
'''
def listString(linkedList):
  ptr = linkedList
  str1 = ''
  while ptr != None:
    str1 += str(ptr['data'])
    ptr = ptr['next']
    if ptr != None:
      str1 += "->"
  str1 = str1
  return str1

'''
Inserts a new node containing the value "value" to the head of the list.
LinkedList is the head of the list to be added to
Value is the data to be stored in the node
'''
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

"""
Helper method: returns a reference to node n in a list counting from zero).
Parameters: the list and an index n
If there is no node n, returns None.
"""
def nthNode(linkedList, n):
    ptr = linkedList
    count = 0
    if n < 0:
        return None
    while ptr != None and count < n:
        ptr = ptr['next']
        count += 1
    return ptr

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

  # Now we swap. We're rotating three items' .next values, so we can't
  # do the really optimized way.
  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)
    myList = switch(myList, 3)
    print "Switching the 4 and the 5.  Resuling list is ", listString(myList)
    myList = switch(myList, 5)  
    myList = switch(myList, 29)  #should result in an error

在 switch() 函数中，我遇到了一个错误，提示说 AttributeError: 'dict' object has no attribute 'next'。我该怎么做才能解决这个问题，让函数正常运行呢？我哪里出错了？

编辑 1：我把参数 list 改成了 j，并且把 switch 函数里的 .next 改成了 ['next']。现在，当我运行 testSwitch() 时，又出现了一个错误：“TypeError: 'NoneType' object has no attribute 'getitem'”。你知道这个错误是怎么回事吗？我检查了代码，感觉在到达测试部分之前不应该返回 None……

错误处理数据结构函数设计类型错误链表属性错误索引操作节点交换

如何在链表中交换指定索引的节点和头节点？

1 个回答

撰写回答