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
}