URL

Reverse Linked List II - LeetCode

Code

https://github.com/syohex/dotnet-study/tree/master/fsharp/leetcode/challenge/202309/reverse_linked_list2/main.fsx

type ListNode =
    | Leaf
    | Node of int * ListNode

let rec toListAppend (nums: int list) (tail: ListNode) : ListNode =
    match nums with
    | [] -> tail
    | h :: t -> Node(h, toListAppend t tail)

let reverseSubList (node: ListNode) (n: int) : ListNode =
    let rec reverseSubList' node n acc =
        if n = 0 then
            toListAppend acc node
        else
            match node with
            | Leaf -> failwith "never reach here"
            | Node(v, next) -> reverseSubList' next (n - 1) (v :: acc)

    reverseSubList' node n []

let rec reverseBetween (head: ListNode) (left: int) (right: int) : ListNode =
    if left = 1 then
        reverseSubList head right
    else
        match head with
        | Leaf -> failwith "never reach here"
        | Node(v, next) -> Node(v, reverseBetween next (left - 1) (right - 1))