[leetcode] flip linked list II

1 subject

Advanced version of linked list turnover , That is, only a part of the linked list is flipped . This requires us to find the head and tail nodes of the list to be flipped , Then turn it over again .

2 thought

• Flip position left To Location right The linked list node of
• This task is divided into two parts
• determine pre_head, tail_next 2. List flip

3 Code

# 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.  determine 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 #  Flip from the first header node 
        else:
            start = pre_head.next
        
        # step 2.  List flip 
        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