python链表的反转方式是什么

编辑: admin 分类: python 发布时间: 2023-05-01 来源:互联网

    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):
            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.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 = 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链表的反转方式是什么的详细内容,更多请关注海外IDC网其它相关文章!

    【本文转自:香港服务器 http://www.1234xp.com 复制请保留原URL】