开发者

python之链表的反转方式

目录
  • python链表的反转
    • 反转链表
    • 题解
  • python反转链表相关技巧
    • 关键公式
      • 链表内指定区间反转
      • 链表中的节点每k个一组翻转
    • 总结

      python链表的反转

      反转链表

      给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

      python之链表的反转方式

      • 输入:head = [1,2,3,4,5]
      • 输出:[5,4,3,2,1]

      python之链表的反转方式

      • 输入:head = [1,2]
      • 输出:[2,1]

      示例 3:

      • 输入: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反转链表相关技巧

      给定一个单链表的头结点pHead(该头节点是有值的,比如在下图,它的val是1),长度为n,反转该链表后,返回新链表的表头。

      要求:空间复杂度 O(1)O(1) ,时间复杂度 O(n)O(n) 。

      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

      关键公式

      抓住几个关键点:

      • cur:原链表的头节点,在反转结束时,cur指向pre的下一个节点
      • pre:原链表的尾节点,也就是反转后链表的头节点。最终返回的是pre。
      • while cur:表示反转循环的条件,这里是判断cur是否为空。也可以根据题目的条件改成其他循环条件
      • 反转链表的尾节点,这里的尾节点是None,后面会提到显式指定。

      对于反转链表的问题,抓住原链表的头节点、原链表的尾节点、反转循环条件、反转链表的尾节点这几个主要角色,基本没什么问题。

      接下来,举两个例子:

      链表内指定区间反转

      链表中的节点每k个一组翻转

      链表内指定区间反转

      将一个节点数为 size 链表 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}

      套用公式

      这道题目和baseline的区别是,是将对整个链表的反转改成链表 m 位置到 n 位置之间的区间反转,来套一下公式:

      • 原链表的头节点:cur:从head出发,再走m-1步,到达cur
      • 原链表的尾节点:pre:cur前面的节点
      • 反转循环条件:for i in range(n,m)
      • 反转链表的尾节点:需要保存下从head出发,再走m-1步,到达cur时,此时pre的位置 prePos。prePos.next是反转链表的尾节点

      和前面的比,需要额外注意下:

      • 需要保存下从head出发,再走m-1步,到达cur时,此时pre的位置 prePos。在反转循环结束后,再进行穿针引线
      • 由于不是对整个链表进行反转,最好新建虚拟头节点dummpyNode,dummpyNode.next指向整个链表

      python之链表的反转方式

      代码实现

      先看下套公式部分的代码:

      # 找到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):
              s开发者_Python培训elf.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
             android     cur.next = pre
                  pre = cur
                  cur = nextNode
                  i = i+1
              
              nextNode = preHead.next
              preHead.next = pre
              if nextNode:
                  nextNode.next = cur
       
              return dummpyNode.next

      链表中的节点每k个一组翻转

      将给出的链表中的节点每 k 个一组翻转,返回翻转后的链表

      如果链表中的节点数不是 k 的倍数,将最后剩下的节点保持原样

      你不能更改节点中的值,只能更改节点本身。

      要求空间复杂度 O(1),时间复杂度 O(n)

      输入:

      {1,2,3,4,5},2

      返回值:

      {2,1,4,3,5}

      套用公式

      这道题目和baseline的区别是,是将对整个链表的反转改成每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 = tmphttp://www.devze.com.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:
                 python     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,后面会提到显式指定。

      想清楚这几个关键点都是如何定义的,基本题目都可以迎刃而解啦。

      总结

      以上为个人经验,希望能给大家一个参考,也希望大家多多支持我们。

      0

      上一篇:

      下一篇:

      精彩评论

      暂无评论...
      验证码 换一张
      取 消

      最新开发

      开发排行榜