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]
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?
Solutions
Solution 1: Simulation
Define a dummy head node dummy, pointing to the head node head of the linked list. Then define a pointer pre pointing to dummy. Start traversing the linked list from the dummy head node. When you traverse to the left node, point pre to this node. Then start traversing right - left + 1 times from this node, and insert the nodes you traverse into the back of pre. Finally, return dummy.next.
The time complexity is $O(n)$, and the space complexity is $O(1)$. Here, $n$ is the length of the linked list.
1 2 3 4 5 6 7 8 9101112131415161718192021222324
# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclassSolution:defreverseBetween(self,head:Optional[ListNode],left:int,right:int)->Optional[ListNode]:ifhead.nextisNoneorleft==right:returnheaddummy=ListNode(0,head)pre=dummyfor_inrange(left-1):pre=pre.nextp,q=pre,pre.nextcur=qfor_inrange(right-left+1):t=cur.nextcur.next=prepre,cur=cur,tp.next=preq.next=curreturndummy.next
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */funcreverseBetween(head*ListNode,leftint,rightint)*ListNode{ifhead.Next==nil||left==right{returnhead}dummy:=&ListNode{0,head}pre:=dummyfori:=0;i<left-1;i++{pre=pre.Next}p,q:=pre,pre.Nextcur:=qfori:=0;i<right-left+1;i++{t:=cur.Nextcur.Next=prepre=curcur=t}p.Next=preq.Next=curreturndummy.Next}