【LeetCode】翻转链表II

1 题目

链表翻转的进阶版，即只翻转链表的某一部分。这就要求我们找到待翻转链表的头结点和尾节点，然后再翻转一下就可以了。

2 思想

• 翻转位置left 到 位置right 的链表节点
• 本任务拆解成两部分
• 确定pre_head, tail_next 2. 链表翻转

3 代码

# 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:
        pre_head = None
        tmp = head
        # step 1. 确定pre_head
        cnt = 1
        while(cnt < left):
            pre_head = tmp
            tmp = tmp.next
            cnt += 1
        
        cnt = 1
        tail_next = head
        while(cnt < right):
            tail_next = tail_next.next
            cnt +=1 
        tail_next = tail_next.next

        
        if pre_head is None:
            start = head # 从第一个头结点开始翻转
        else:
            start = pre_head.next
        
        # step 2. 链表翻转
        nxt = start.next
        tmp = start
        while(start and nxt != tail_next):
            tmp2 = nxt.next #
            nxt.next = start
            start = nxt
            nxt = tmp2
        
        if pre_head is None:
            head = start
        else:
            pre_head.next = start
        
        tmp.next = tail_next
        return head