Pythonのリンクリスト内のノードを交換するプログラム

リスト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番目のノードであるため、これらは交換されます。

これを解決するには、次の手順に従います-

• temp：=L
• 0からk-2の範囲のiについては、
  • temp：=次のtemp
• firstNode：=temp
• secondNode：=L
• next of tempがnullでない場合は、
  • 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, ]