92反转链表II

cong12586 2021-03-18 原文

# Definition for singly-linked list.
# 这道题还是有点复杂的，但是是有套路的，套用反转链表的想法
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:
        # 首先定义一个前置根节点，这样做是用来当反转链表的开头为1的时候，我们也能够反转它。
        node_None = ListNode(0)
        # 组成新的链表。
        node_None.next = head
        # 定义变量用来遍历链表。
        pre = node_None
        # 遍历，找到我们需要反转链表段的开头。
        for i in range(left - 1):
            pre = pre.next
        # 此时pre在需要反转的链表左端的前一个节点。
        # 因为我们前置了一个根节点，所以一定会有这个节点。
        # 找到第一个需要反转的节点。
        node = pre.next
        # 然后定义一个变量，用来反转链表。
        node1 = pre
        for i in range(right - left + 1):
            # 这里是有顺序的，不能够把顺序写乱。
            # node的next指向前面，node1 向下一个，node 向下一个，这样我们就反转了一个节点，
            # 然后接着遍历。
            node.next,node1,node, = node1,node,node.next
        # 当循环结束的时候， node 为 反转链表右端的下一个节点，也肯能为空。
        # node1位反转链表右端那个节点。
        # 因此我们需要将整个反转链表段和之前的链表重新连接，然后组成反转之后的链表。
        pre.next.next = node
        pre.next = node1
        # 注意，这里我们需要返回node_None的下一个节点，
        # 不能返回head节点，因为有可能head节点已经被反转了。
        return node_None.next





a = ListNode(1)
b = ListNode(2)
c = ListNode(3)
d = ListNode(4)
e = ListNode(5)
f = ListNode(6)
a.next = b
b.next = c
c.next = d
d.next = e
e.next = f
# a.next = b
# a.next = b


A = Solution()
print(A.reverseBetween(a,2,4))