Python データ構造の反転リンク リスト

リンク リストを反転する

例: リンク リスト 1->2->3->null がある場合、反転されたリンク リストは 3->2->1->null になります

比較的簡単な方法は「抽出法」を使うことです。つまり、最初に新しい空のノードを作成し、次にリンク リスト全体を走査し、走査されたノードが新しく作成されたリンク リストのヘッド ノードを指すようにします。

たとえば、手順は次のとおりです:

1. 新しい空のノードを作成します: なし
2. 2->1-> なし
4. ; 2->1->なし

コードは非常に簡単です:

""" 
Definition of ListNode 
 
class ListNode(object): 
 
 def __init__(self, val, next=None): 
  self.val = val 
  self.next = next 
""" 
class Solution: 
 """ 
 @param head: The first node of the linked list. 
 @return: You should return the head of the reversed linked list. 
     Reverse it in-place. 
 """ 
 def reverse(self, head): 
  temp = None 
  while head: 
   cur = head.next 
   head.next = temp 
   temp = head 
   head = cur 
  return temp 
  # write your code here

もちろん、もう少し難しい解決策もあります。リンクリスト内のノードのリンク解除とリンクを順番に行うメソッドのインプレースフリップコードを書くことができます:

""" 
Definition of ListNode 
 
class ListNode(object): 
 
 def __init__(self, val, next=None): 
  self.val = val 
  self.next = next 
""" 
class Solution: 
 """ 
 @param head: The first node of the linked list. 
 @return: You should return the head of the reversed linked list. 
     Reverse it in-place. 
 """ 
 def reverse(self, head): 
  if head is None: 
   return head 
  dummy = ListNode(-1) 
  dummy.next = head 
  pre, cur = head, head.next 
  while cur: 
   temp = cur 
   # 把摘链的地方连起来 
   pre.next = cur.next 
   cur = pre.next 
   temp.next = dummy.next 
   dummy.next = temp 
  return dummy.next 
  # write your code here

リンクを解除するときは、接続を忘れないように注意してください。削除された場所をもう一度

読んでいただきありがとうございます、皆さんのお役に立てれば幸いです、このサイトをサポートしていただきありがとうございます!

Python データ構造のリンク リストの反転に関連するその他の記事については、PHP 中国語 Web サイトに注目してください。