鏈表是一種重要的數據結構,它有許多應用。在Python中,鏈表可以通過使用類和對象實現。鏈表有許多操作,其中轉置操作是一種重要的操作。本文將介紹如何使用Python編寫鏈表轉置函數。
下面是鏈表轉置函數的實現代碼:
class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self): self.head = None def addNode(self, data): if self.head is None: self.head = Node(data) else: currentNode = self.head while currentNode.next is not None: currentNode = currentNode.next currentNode.next = Node(data) def printList(self): currentNode = self.head while currentNode is not None: print(currentNode.data, end=' ') currentNode = currentNode.next def reverseList(self): previousNode = None currentNode = self.head while currentNode is not None: nextNode = currentNode.next currentNode.next = previousNode previousNode = currentNode currentNode = nextNode self.head = previousNode
在上面的代碼中,我們定義了一個Node類來表示鏈表中的節點。每個節點都有一個data屬性和一個next屬性,分別表示節點的數據和下一個節點的指針。我們還定義了一個LinkedList類,它包含一個指向鏈表頭部的指針。
鏈表轉置函數reverseList()使用一個循環來遍歷整個鏈表。它使用三個指針previousNode、currentNode和nextNode。previousNode指向前一個節點,currentNode指向當前節點,nextNode指向下一個節點。該函數使用currentNode的next屬性來迭代鏈表,同時使用previousNode和nextNode來更改鏈表中節點之間的指針。最后,我們將鏈表的頭指針指向previousNode。
這是一個示例程序,它演示了如何創建一個鏈表,將其打印,然后將其轉置并再次打印:
ll = LinkedList() ll.addNode(1) ll.addNode(2) ll.addNode(3) ll.addNode(4) ll.addNode(5) ll.printList() print() ll.reverseList() ll.printList()
該程序將輸出:
1 2 3 4 5 5 4 3 2 1
可以看到,我們成功地轉置了鏈表,使其與原始鏈表相反。