用 Python 编写的用于交换链接列表中节点的程序

pythonserver side programmingprogramming更新于 2025/12/7 15:40:17

假设我们有一个列表 L 和另一个值 k。我们必须交换从开始到结束的第 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
对于 0 到 k-2 范围内的 i，执行
- temp := next of temp
firstNode := temp
secondNode := L
当 next of temp 不为空时，执行
- secondNode := next of secondNode
- temp := next of 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))