92. Reverse Linked List II
Medium
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 <= 5001 <= left <= right <= n
Follow up: Could you do it in one pass?
Runtime: 0 ms, faster than 100%
Memory Usage: 2.1 MB, less than 16.81%
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseBetween(head *ListNode, left int, right int) *ListNode {
res := &ListNode{}
r := res
stack := make([]int, 0)
count := 1
for head != nil {
if count == left {
break
}
res.Next = head
head = head.Next
res = res.Next
count++
}
// 要反轉的部分放到 stack
for head != nil {
stack = append(stack, head.Val)
if count == right {
head = head.Next
break
}
count++
head = head.Next
}
for len(stack) != 0 {
res.Next = &ListNode{ Val:stack[len(stack) - 1] }
stack = stack[:len(stack) - 1]
res = res.Next
}
res.Next = head
return r.Next
}
Last modified 6mo ago