Every programmer must forget about how to reverse a linked list.
while cur:
nxt = cur.next
cur.next = pre
pre, cur = cur, nxt
Q: 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 = 4
Output: [1,4,3,2,5]
Example 2:
Input: head = [5], left = 1, right = 1
Output: [5]
S1:
# 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: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
vhead = ListNode(0, head)
origin = vhead
for i in range(left-1):
origin = origin.next
pre, cur, nxt = None, origin.next, None
cnt = 0
while cur and cnt < right - left + 1:
nxt = cur.next
cur.next = pre
pre, cur = cur, nxt
cnt += 1
origin.next.next = cur
origin.next = pre
return vhead.next
#O(n), O(1)
Q:
S1:
