Computer >> Máy Tính >  >> Lập trình >> Python

Chương trình hoán đổi các nút trong danh sách được liên kết bằng Python

Giả sử chúng ta có một danh sách L và một giá trị khác k. Chúng ta phải hoán đổi nút thứ k từ đầu và nút thứ k từ cuối và trả về danh sách cuối cùng ở cuối.

Vì vậy, nếu đầu vào giống như L =[1,5,6,7,1,6,3,9,12] k =3, thì đầu ra sẽ là [1,5,3,7,1,6, 6,9,12], nút thứ 3 từ đầu là 6 và từ cuối là 3, vì vậy chúng được đổi chỗ cho nhau.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

  • tạm thời:=L
  • đối với tôi trong phạm vi từ 0 đến k-2, thực hiện
    • temp:=tiếp theo của temp
  • firstNode:=temp
  • secondNode:=L
  • trong khi tiếp theo của tạm thời không null, hãy thực hiện
    • secondNode:=next of secondNode
    • temp:=tiếp theo của temp
  • hoán đổi giá trị của FirstNode và giá trị của secondNode
  • trả về L

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

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

Đầu ra

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