単一リンク リストのヘッド ノードを提供します。そのノードを反転してください。リンクされたリスト、そして反転されたリンクされたリストを返します。
##入力 : head = []
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: """ 解题思路: 1.新建一个头指针 2.遍历head链表,依次在新的头节点位置插入,达到反转的效果 """ def reverseList(self, head: ListNode) -> ListNode: # 循环 new_head = None while head: per = head.next # pre 为后置节点,及当前节点的下一个节点 head.next = new_head # 插入头节点元素 new_head = head # 把串起来的链表赋值给头指针 head = per # 向后移一个单位 return new_head # 返回一个新的链表Python反転リンクリスト関連スキル
#{1,2,3}
#戻り値:
{3,2,1}
まず、最も基本的な逆リンク リストのコードを見てみましょう:
# -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: # 返回ListNode def ReverseList(self, pHead): # write code here cur = pHead pre = None while cur: nextNode = cur.next cur.next = pre pre = cur cur = nextNode return pre
主要な式いくつかを見てみましょう。キーポイント:
リンク リスト内の指定された間隔を反転する
リンク リスト内の k 個のノードごとに反転する リンク リストで指定された間隔の反転
サイズのノード番号を持つリンク リストの m 位置と n 位置の間の間隔を反転するには、時間計算量 O(n) と空間計算量 O(1) が必要です)。
要件: 時間計算量 O(n)、空間計算量 O(n)上級: 時間計算量 O(n)、空間計算量 O(1)
入力:
{1,2,3,4,5},2,4戻り値:
式を適用する{1,4,3,2,5}
この質問とベースラインの違いは、リンク リスト全体を、リンク リストの m 位置と n 位置の間の間隔の反転に適用します。式を適用しましょう:
元のリンク リストのヘッド ノード: cur: head から開始して、 m-1 ステップを実行して cur
## の前のノード
#逆ループ条件 : for i in range(n,m)最初に数式部分のコードを見てみましょう:
# 找到pre和cur i = 1 while i<m: pre = cur cur = cur.next i = i+1 # 在指定区间内反转 preHead = pre while i<=n: nextNode = cur.next cur.next = pre pre = cur cur = nextNode i = i+1コードの針と糸の部分を通す:
nextNode = preHead.next preHead.next = pre if nextNode: nextNode.next = cur完全なコード:
class ListNode: def __init__(self, x): self.val = x self.next = None class Solution: def reverseBetween(self , head , m , n ): # write code here dummpyNode = ListNode(-1) dummpyNode.next = head pre = dummpyNode cur = head i = 1 while i<m: pre = cur cur = cur.next i = i+1 preHead = pre while i<=n: nextNode = cur.next cur.next = pre pre = cur cur = nextNode i = i+1 nextNode = preHead.next preHead.next = pre if nextNode: nextNode.next = cur return dummpyNode.nextk グループごとにリンク リスト内のノードを反転するノードを反転する指定されたリンク リストで k グループごとにフリップを返します。 最後のリンク リスト
##リンク リスト内のノードの数が k の倍数でない場合、最後に残ったノードをそのまま保持します
ノード内の値は変更できません。変更できるのはノード自体のみです。
空間計算量 O(1)、時間計算量 O(n)が必要です入力:
{1,2, 3, 4,5},2戻り値:
{2,1,4,3,5}式を適用する
この質問とベースラインの違いは、リンク リスト全体の反転が k 個の反転のグループに変更されることです。ノードの数が k の倍数でない場合、残り ノードはそのまま残ります。 まずセクションで見てみましょう。位置 1 から位置 k までのリンク リストに直面するとします:
元のリンク リストのヘッド ノード: cur: head から開始して k -1 ステップを進み、cur
に到達します原链表的尾节点:pre:cur前面的节点
反转循环条件:for i in range(1,k)
反转链表的尾节点:先定义tail=head,等反转完后tail.next就是反转链表的尾节点
先看下套公式部分的代码:
pre = None cur = head tail = head i = 1 while i<=k: nextNode = cur.next cur.next = pre pre = cur cur = nextNode i = i+1
这样,我们就得到了1 位置1-位置k的反转链表。
此时:
pre:指向反转链表的头节点
cur:位置k+1的节点,下一段链表的头节点
tail:反转链表的尾节点
那么,得到位置k+1-位置2k的反转链表,就可以用递归的思路,用tail.next=reverse(cur,k)
需要注意:如果链表中的节点数不是 k 的倍数,将最后剩下的节点保持原样
i = 1 tmp = cur while i<=k: if tmp: tmp = tmp.next else: return head i = i+1
代码实现
完整代码:
class ListNode: def __init__(self, x): self.val = x self.next = None class Solution: def reverseKGroup(self , head , k ): # write code here return self.reverse(head, k ) def reverse(self , head , k ): pre = None cur = head tail = head i = 1 tmp = cur while i<=k: if tmp: tmp = tmp.next else: return head i = i+1 i = 1 while i<=k: nextNode = cur.next cur.next = pre pre = cur cur = nextNode i = i+1 tail.next = self.reverse(cur, k) return pre
好了,抓住几个关键点:
cur:原链表的头节点,在反转结束时,cur指向pre的下一个节点
pre:原链表的尾节点,也就是反转后链表的头节点。最终返回的是pre。
while cur:表示反转循环的条件,这里是判断cur是否为空。也可以根据题目的条件改成其他循环条件
反转链表的尾节点,这里的尾节点是None,后面会提到显式指定。
以上がPythonのリンクリストの反転メソッドとは何ですかの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。