博客

前言

1. 秋招结束，恢复一下思维体操，重新先刷一下之前的刷过的基础题目，之前都是使用cpp，Java。之后鉴于工作方向为数字IC相关方向，只使用python来实现，也是对这一工具语言的强化练习。

题目

1. 206. 反转链表
        
        
2. 92. 反转链表 II
       
       

思路与代码实现

1. 题目1和2都是最基本的链表指针问题，只要维护好前后指针即可顺利解决此类习题，由于本期主要目的是熟悉python的用法，因此不赘述思路，直接附上增加注释的python代码即可。
2. 206. 反转链表

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 指定当前节点到头结点
        cur = head
        # 指定新的空节点
        pre = None
        # 遍历当前节点
        while(cur != None):
            # 备份下一节点
            next = cur.next
            # 翻转指针
            cur.next = pre
            # 更新双指针
            pre = cur
            cur = next
        return pre

3. 92. 反转链表 II

class Solution:
    def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
        
        dummy_node = ListNode(-1)
        dummy_node.next = head
        # 移动pre指针至待翻转节点的前一个节点
        pre = dummy_node
        for _ in range(left - 1):
            pre = pre.next

        # 待翻转的第一个节点为cur节点
        cur = pre.next
        # 翻转部分节点的处理：穿针引线法
        for _ in range(right - left):
            # 备份当前待翻转第一个节点的下一节点
            next = cur.next
            # 跳节点向后连接
            cur.next = next.next
            # 跳节点向前连接
            next.next = pre.next
            # 跳节点向后连接
            pre.next = next
        return dummy_node.next

后语

1. 保持节奏，稳步前进！！！