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 <= 500
  • 1 <= 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
}
​
​