您的位置：首页 > 技术中心 > 其他 >

python链表的反转方式是什么

时间：2023-04-29 23:32

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 = nextclass 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 = Noneclass 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和curi = 1while i<m:    pre = cur    cur = cur.next    i = i+1 # 在指定区间内反转preHead = prewhile i<=n:    nextNode = cur.next    cur.next = pre    pre = cur    cur = nextNode    i = i+1

穿针引线部分代码：

nextNode = preHead.nextpreHead.next = preif 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 = Nonecur = headtail = head  i = 1while 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 = 1tmp = curwhile 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

好了，抓住几个关键点：