Leetcode-14。Python对列表倒排问题的回答,leetcode14,链表,反转,类,题目,python,解答

发表时间:2021-05-11

引言

反转类题目,可以通过迭代与递归来解决,这篇文章主要讲述迭代方法,递归方法会在后面介绍到。

206. 反转链表

反转一个单链表。

示例:

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

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        # 处理特殊情况
        if head == None or head.next == None:
            return head
        
        pre = None
        cur = head
        # t是中间指针,链表题中经常用到
        while cur != None:
            t = cur.next
            cur.next = pre
            pre = cur
            cur = t
        
        return pre

92. 反转链表 II

给你单链表的头指针 head 和两个整数 m 和 n ,其中 m <= n 。请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表 。

示例:

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

思路:

我们需要两个指针pre和cur。向前推进cur指针,prev指针跟随其后,直到cur指针到达从链表头起的第m个结点。
tail指针指向从链表头起的第m 个结点,此结点是反转后链表的尾部,故称为tail。con指针指向第m个结点的前一个结点,此结点是新链表的头部。
当cur指针抵达第m个结点后,迭代地反转链接,直到完成指向第n个结点的链接。此时,pre指针会指向第n个结点。
这时候,我们使用con指针来连接pre指针,类似地,我们利用tail指针来连接pre指针之后的结点(第n+1个结点)。

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
        pre = None
        cur = head
        count = 1
        while count < left:
            pre = cur
            cur = cur.next
            count += 1
        # 循环结束时,cur指针指向left位置,pre指针指向前一个位置
        # 记录
        cont = pre
        tail = cur
        while count <= right:
            temp = cur.next
            cur.next = pre
            pre = cur
            cur = temp
            count += 1
        # 循环结束时,pre指针指向right位置,cur指针指向right+1位置
        if cont:
            cont.next = pre
        else:
            head = pre
        tail.next = cur
        
        return head

出了错误的话,可以用如下方法来验证

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


# 生成链表的函数
def create_node_list(arr):
    head = ListNode(arr[0])
    cur = head
    for i in range(1, len(arr)):
        cur.next = ListNode(arr[i])
        cur = cur.next
    return head


class Solution:
    def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
        pre = None
        cur = head
        count = 1
        while count < left:
            pre = cur
            cur = cur.next
            count += 1
        # 循环结束时,cur指针指向left位置,pre指针指向前一个位置
        # 记录
        cont = pre
        tail = cur
        while count <= right:
            temp = cur.next
            cur.next = pre
            pre = cur
            cur = temp
            count += 1
        # 循环结束时,pre指针指向right位置,cur指针指向right+1位置
        if cont:
            cont.next = pre
        else:
            head = pre
        tail.next = cur

        curr = head
        data = []
        while curr:
            data.append(str(curr.val))
            curr = curr.next
        print('(Head) ' + ' -> '.join(data) + ' (Tail)')

        return head



if __name__ == '__main__':
    arr = [1, 2, 3, 4, 5]
    left = 2
    right = 4
    head = create_node_list(arr)
    s = Solution()
    s.reverseBetween(head, left, right)

25. K 个一组翻转链表

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

示例:

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

思路:

链表分区为已翻转部分+待翻转部分+未翻转部分。
每次翻转前,要确定翻转链表的范围,这个必须通过k次循环来确定,需记录翻转链表前驱pre和后继next,方便翻转完成后把已翻转部分和未翻转部分连接起来。同时,k个一组的链表的头和尾用start和end表示,start初始位于k个链表的第一个,而end初始位于其前驱。经过k次循环,end 到达末尾,记录待翻转链表的后继pre= end.next,并把end 断开。反转链表。然后将三部分链表连接起来,然后重置pre和end 指针,然后进入下一次循环。
结合下面图进行理解:
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        # 构造虚拟头结点
        dummy = ListNode(0)
        dummy.next = head
        # 构造三个指针
        pre = dummy
        end = dummy     # 经过K次循环,end到达末尾
        start = head

        while True:
            # 经过K次循环,end到达一组的末尾
            for _ in range(k):
                end = end.next
                if end == None:
                    break
            # 链表到达末尾(差一个)
            if end ==None:
                break
            
            third = end.next
            end.next = None
            # 反转大小为k的链表(返回反转后的头节点)
            temp = self.reverse(start)
            # 前面已完成反转部分的链表接上这个头节点
            pre.next = temp
            # 更新这几个指针
            pre = start
            end = start
            start.next = third
            start = start.next
        return dummy.next
	
	# 反转
    def reverse(self,head):
        dummy = ListNode(0)
        pre = dummy
        cur = head

        while cur != None:
            temp = cur.next
            cur.next = pre
            pre = cur
            cur = temp
        return pre

如果对您有帮助,麻烦点赞关注,这真的对我很重要!!!如果需要互关,请评论或者私信!
在这里插入图片描述


文章来源互联网,如有侵权,请联系管理员删除。邮箱:417803890@qq.com / QQ:417803890

微配音

Python Free

邮箱:417803890@qq.com
QQ:417803890

皖ICP备19001818号-4
© 2019 copyright www.pythonf.cn - All rights reserved

微信扫一扫关注公众号:

联系方式

Python Free