Reverse from position m To n The linked list of . Please use a scan to complete the inversion .
explain :
1 ≤ m ≤ n ≤ Chain length .
Example :
Input : 1->2->3->4->5->NULL, m = 2, n = 4
Output : 1->4->3->2->5->NULL
The question requires a walk through . Deal with the problem of linked list , It usually generates a dummy Node, bring dummy Node Point to the head node of the list . In addition, you need to locate the start node where you want to reverse the list , And mark the previous node of the start node , So that in the process of flipping , This node can always be found .
Suppose you want to reverse the list segment as follows :1—>2—>3
The turning process is as follows :
pre—>1—>2—>3
pre—>2—>1—>3
pre—>3—>2—>1
class Solution:
def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
dummyNode = ListNode(-1) # Master as one dummy node
dummyNode.next = head
pre = dummyNode
for i in range(m-1):
pre = pre.next # Navigate to the previous node that started flipping the list
cur = pre.next
for i in range(m,n): # Start reverse
temp = cur.next
cur.next = temp.next
temp.next = pre.next
pre.next = temp
return dummyNode.next