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

問題の説明: リンク リストが与えられた場合、各ノードが右に k 位置移動するようにリンク リストを回転します。ここで、k は負でない数です

例: リンク リスト 1->2->3 が与えられた場合-> 4->5->null and k=2; return 4->5->1->2->3->null

まず、目的を見てみましょう実際、この質問は別の方法で次のように説明できます。k 値が与えられた場合、この例では、k 番目のノードから始まるリンク リストの部分をリンク リストの最後から先頭に移動します。 、実際には 4->5 と移動しています。この部分はリンクされたリスト全体の先頭に移動され、4->5->1->2->3->null になります。ただし、質問では k のサイズが指定されていないことに注意してください。たとえば、k がリンク リストの長さより大きい場合、最初に k を使用してリンク リストの長さの残りを見つける必要があります。 、k = 7 の場合、上記の例では、リンク リスト全体の先頭に 4->5 が移動します。

したがって、この質問の考え方は次のように要約できます:

1. まず、リンクされたリスト全体の長さを求めます
2. 必要なリンクされたリストの部分の前任者を見つけます。 k の値 (例では 3) に基づいて移動します
3 . プリカーサーの後のリンクされたリストを切断し、後半を移動します

コードは次のとおりです:

# Definition for singly-linked list. 
# class ListNode: 
#   def __init__(self, x): 
#     self.val = x 
#     self.next = None 
 
class Solution: 
  # @param head: the list 
  # @param k: rotate to the right k places 
  # @return: the list after rotation 
  def rotateRight(self, head, k): 
    if head is None: 
      return head 
    cur = head 
    count = 1 
    # 计算链表长度 
    while cur.next: 
      cur = cur.next 
      count += 1 
    # 为节省代码量，这里是一个很有技巧的处理：用尾节点链接头结点 
    cur.next = head 
    # 此处，k为cur从尾节点到要断开部分的前驱需走的步数 
    k = count - k % count 
    # 找到前驱 
    while k != 0: 
      cur = cur.next 
      k -= 1 
    # 断开 
    head = cur.next 
    cur.next = None 
    # 因为首尾已经相连，所以直接返回前驱后面的那个节点即可，此处引用为head 
    return head 
    # write your code here

21 行が端から端まで接続されているため、コードの量が大幅に節約されます。実際、これまでのアイデアで説明した段階的な手順に従えば問題ありません。しかし、このテクニックは本当に素晴らしく、学ぶ価値があります。具体的な詳細はコードのコメントに書きました。

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

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