专栏首页用户2133719的专栏常见编程模式之就地反转链表

常见编程模式之就地反转链表

6. 就地反转链表(In-place Reversal of a LinkedList)

基本原理及应用场景

在很多问题中,我们需要对一个链表中的节点连接进行反转,且通常需要原地进行,即不能使用额外的存储空间。这时我们可以使用就地反转链表模式,该模式本质上是一种迭代解法,流程如下图所示。首先设置一个变量 current 指向链表头部,以及另一个变量 previous 指向当前处理节点的前一个节点。下一步我们需要将当前节点 current 进行反转,将其指向前一个节点 previous,然后将 previous 指向当前节点,再将 current 移动到下一个节点,开始迭代直至遍历完成。

经典例题

206. 反转链表(Easy)

反转一个单链表。

「示例」

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

这道题可以采用就地反转链表模式,即迭代方法,参考上面的讲解,代码实现如下:

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        curr, pre = head, None
        while curr:
            temp_next = curr.next
            curr.next = pre
            pre = curr
            curr = temp_next
        return pre

当然这道题也可以采用递归实现,但是使用了隐式的栈空间,且不是非常好理解:

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        p = self.reverseList(head.next) # 一直递归到最后一个元素之前,返回p为head.next(即最后一个节点)
        head.next.next = head # 在当前递归中将head.next的下一个节点反转为head
        head.next = None # 清除当前节点的下一个节点,防止循环(实际上只对最后一个节点有用,前面的会自动修改)
        return p

递归的原理可以通过下图理解(来自 Leetcode-王尼玛):

92. 反转链表 II(Medium)

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

1 ≤ m ≤ n ≤ 链表长度。

「示例:」

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

这道题可以采用就地反转链表模式,由于只翻转部分位置,所以需要设置两个额外的节点进行标记,翻转完成后将翻转部分和未翻转的部分进行拼接。具体的代码实现如下:

class Solution:
    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
        if not head: return None
        cur, prev = head, None
        while m > 1: # 将cur移到开始反转的位置,prev移到其前一个节点
            prev = cur
            cur = cur.next
            m, n = m - 1, n - 1 # 注意对n也进行处理,相当于n=n-m+1
        tail, con = cur, prev # 设置两个额外节点,用于之后拼接链表
        
        while n: # 执行就地反转链表模式
            temp_next = cur.next
            cur.next = prev
            prev = cur
            cur = temp_next
            n -= 1
        # 拼接头部
        if con:
            con.next = prev
        else:
            head = prev
        # 拼接尾部(实际上最开始的prev被丢弃了)
        tail.next = cur
        return head

本题也可以采用递归方法进行求解,我们先定义一个反转前 n 个节点的子函数,然后递归至起始位置开始反转即可:

class Solution:
    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
        def reverseN(head, n):
            if n == 1:
                return head
            p = reverseN(head.next, n - 1)
            successor = head.next.next # 始终指向反转节点的后一个节点
            head.next.next = head # 反转链表
            head.next = successor # 将最后一个节点指向后面未反转的部分
            return p
        if m == 1: return reverseN(head, n)
        head.next = self.reverseBetween(head.next, m - 1, n - 1)
        return head

25. K 个一组反转链表(Hard)

给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。k 是一个正整数,它的值小于或等于链表的长度。 如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。

「示例」

给你这个链表:1->2->3->4->5

  • 当 k = 2 时,应当返回: 2->1->4->3->5
  • 当 k = 3 时,应当返回: 3->2->1->4->5

这道题同样可以使用就地反转链表模式,我们需要构建一个反转子链表的函数,然后遍历目标链表,达到 k 个则进行反转,并将其拼接回主链表中。这里的关键技巧是通过哑结点来保证每次相同的遍历次数,以及方便最后的返回。具体的代码实现如下:

class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        def reverse(head, tail):
            # 翻转一个子链表,并且返回新的头与尾
            prev = tail.next # 指向尾节点的下一个节点
            curr = head
            while prev != tail: # 不能用tail.next判断,其指向已经改变
                temp_next = curr.next
                curr.next = prev
                prev = curr
                curr = temp_next
            return tail, head
        
        dummy = ListNode(0) # 设置一个哑结点,方便进行k次遍历(作为pre)以及最终的返回
        dummy.next = head
        pre = dummy # pre为子链表的前一个节点,用于将子链表接回原链表

        while head:
            tail = pre
            # 查看剩余的长度是否大于等于k
            for i in range(k): # 从起始节点的前一个结点开始,刚好k次到尾部
                tail = tail.next
                if not tail:
                    return dummy.next # 不满足直接返回
            temp_next = tail.next # 记录子链表的下一个节点
            head, tail = reverse(head, tail) # 反转子链表
            # 把子链表接回原链表,并设置新的pre与head
            pre.next = head
            tail.next = temp_next
            pre = tail
            head = tail.next
        
        return dummy.next

本文分享自微信公众号 - 口仆(roito33),作者:口仆

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-09-17

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 《剑指 offer》刷题记录之:字符串 & 链表

    这道题的关键在于如何执行替换操作,如果我们使用常规的从前往后遍历字符串替换空格,由于需要将 1 个字符替换为 3 个字符,因此替换时需要将当前字符后面的所有字符...

    口仆
  • 《剑指 offer》刷题记录之:树 & 栈和队列

    其中每个子树的遍历顺序同样满足对应的前序或中序遍历顺序。对于这一题,我们可以采用「递归」或者「迭代」(循环)的方式来求解。递归的方法相对来说要更加简洁一些,而迭...

    口仆
  • 常见编程模式之双指针

    双指针模式指使用两个一前一后的指针遍历数据结构,直到某个指针触发停止条件。该模式常用于在有序数组或链表中搜索元素对。使用双指针的好处在于和单指针相比,不用去连续...

    口仆
  • LeetCode - 两两交换链表中的节点

    该题是第24题,这题一开始我还想了好一会儿,后来发现,好像这样子就好了。递归真的是能用就用,实在是因为递归写起来简单啊。

    晓痴
  • 算法:数组和链表-实战

    因为只是两两的交换,那么我们把第一二位作为一个整体,每次迭代都同时处理两个。一次迭代需要重新指向多少次呢?

    营琪
  • 【Leetcode】61.旋转链表

    昨晚吃火锅吃撑了回来这道题,还算顺利~~ 链表的题目,其实就是在考指针交换,这个题目先让链表连成一个环,然后再切开就可以完成了。

    Leetcode名企之路
  • 翻转链表 II

    一份执着✘
  • LeetCode - 反转链表

    原题地址:https://leetcode-cn.com/problems/reverse-linked-list/)

    晓痴
  • leetcode链表之环路检测

    有环链表的定义:在链表中某个节点的next元素指向在它前面出现过的节点,则表明该链表存在环路。

    codecraft
  • 初级算法(2)-链表

    表的删除就是指针的移动,将待删除节点的指针移动到下一个节点 题1:删除某个链表中给定的(非末尾)节点,你将只被给定要求被删除的节点。 虽然我们并不知道,这个节点...

    方丈的寺院

扫码关注云+社区

领取腾讯云代金券