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

引言

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

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

---

如果对您有帮助，麻烦点赞关注，这真的对我很重要！！！如果需要互关，请评论或者私信！

---