Pythonでリンクリストの内部ノードを逆にするプログラム

リンクリストがあり、2つの値iとjもあるとすると、リンクリストをiからj番目のノードに逆にする必要があります。そして最後に、更新されたリストを返します。

したがって、入力が[1,2,3,4,5,6,7,8,9] i =2 j =6の場合、出力は[1、2、7、6、5、4 、3、8、9、]

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

• prev_head：=nullと同じ値で、ノードを指すリンクリストノードを作成します
• prev：=prev_head、curr：=node
• 0からiまでのすべての値を繰り返し、実行します
  • prev：=curr、curr：=next of curr
• rev_before：=prev、rev_end：=curr
• 0から（j --i）までのすべての値を反復処理し、実行します
  • tmp：=次のcurr
  • 次のcurr：=prev
  • prev、curr：=curr、tmp
• rev_beforeの次：=prev、rev_end.next：=curr
• prev_headの次を返す

理解を深めるために、次の実装を見てみましょう。

例

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(']')

class Solution:
   def solve(self, node, i, j):
      prev_head = ListNode(None, node)
      prev, curr = prev_head, node

      for _ in range(i):
         prev, curr = curr, curr.next
   
      rev_before, rev_end = prev, curr

      for _ in range(j - i + 1):
         tmp = curr.next
         curr.next = prev
         prev, curr = curr, tmp

      rev_before.next, rev_end.next = prev, curr

      return prev_head.next

ob = Solution()
head = make_list([1,2,3,4,5,6,7,8,9])
i = 2
j = 6
print_list(ob.solve(head, i, j))

入力

[1,2,3,4,5,6,7,8,9], 2, 6

出力

[1, 2, 7, 6, 5, 4, 3, 8, 9, ]