動機

就reverse

Problem

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

 

Example 1:

Input: head = [1,2,3,4,5], left = 2, right = 4Output: [1,4,3,2,5]

Example 2:

Input: head = [5], left = 1, right = 1Output: [5]

 

Constraints:

  • The number of nodes in the list is n.
  • 1 <= n <= 500
  • -500 <= Node.val <= 500
  • 1 <= left <= right <= n

 

Follow up: Could you do it in one pass?

Sol

def help(i,j):
    new_goal = i
    k = i.next
    while k!=j:
        
        tmp = k.next
        k.next = i
        i = k
        k = tmp
    new_goal.next = j
    return i
class Solution:
    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
        a = head
        prev = head
        for _ in range(0,m-1):
            if a:
                prev = a
                a = a.next
            else:
                break
        b = a
        for _ in range(0,n-m):
            if b:
                b = b.next
            else:
                break
        if b:
            b = b.next
        if a == head:
            return help(a,b)
        else:
            prev.next = help(a,b)
            return head