Python連結串列節點交換程式

假設我們有一個列表L和另一個值k。我們需要交換從列表開頭和結尾數起的第k個節點，並在最後返回最終列表。

例如，如果輸入為L = [1,5,6,7,1,6,3,9,12]，k = 3，則輸出將為[1,5,3,7,1,6,6,9,12]，從開頭數起的第3個節點是6，從結尾數起的第3個節點是3，因此它們被交換了。

為了解決這個問題，我們將遵循以下步驟：

  • temp := L
  • 對於 i 從 0 到 k-2，執行：
    • temp := temp 的下一個節點
  • firstNode := temp
  • secondNode := L
  • 當 temp 的下一個節點不為空時，執行：
    • secondNode := secondNode 的下一個節點
    • temp := temp 的下一個節點
  • 交換 firstNode 和 secondNode 的值
  • 返回 L

示例

讓我們來看下面的實現以更好地理解：

class ListNode:
   def __init__(self, data, next = None):
      self.val = data
      self.next = next

def make_list(elements):
   head = ListNode(elements[0])
   for element in elements[1:]:
      ptr = head
      while ptr.next:
         ptr = ptr.next
      ptr.next = ListNode(element)
   return head

def print_list(head):
   ptr = head
   print('[', end = "")
   while ptr:
      print(ptr.val, end = ", ")
      ptr = ptr.next
   print(']')
def solve(L, k):
   temp = L
   for i in range(k-1):
      temp = temp.next
   firstNode = temp
   secondNode = L
   while temp.next:
      secondNode = secondNode.next
      temp = temp.next
   firstNode.val , secondNode.val = secondNode.val , firstNode.val
   return L

L = [1,5,6,7,1,6,3,9,12]
k = 3
print_list(solve(make_list(L), k))

輸入

[1,5,6,7,1,6,3,9,12], 3

輸出

[1, 5, 3, 7, 1, 6, 6, 9, 12, ]

更新於：2021年10月6日

964 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告