Thursday, February 13, 2014

Reverse List Every K Node

Today I found an question and decide to use F# pattern match to give it a try.

The question is reverse a list every k node. For example, if the input list is [1; 2; 3; 4; 5; 6; 7; 8; 9; 10] and k = 3, the output will be [3; 2; 1; 6; 5; 4; 9; 8; 7; 10].

When I use pattern matching, I always like recursive implementation.

 let arr = [1..10]  
 let rec reverse arr i =   
   let reverse2 arr =   
     arr |> List.rev  
   let rec getHeadTail arr i =   
     match i with  
     | 0 -> ([], arr)  
     | _ ->   
       match arr with   
       | [] -> ([], [])  
       | h::t ->   
         let (head,tail) = getHeadTail t (i-1)  
         ([h]@head, tail)  
   let headArr, tail = getHeadTail arr i  
   match tail with  
   | [] -> reverse2 headArr  
   | _ -> reverse2 headArr @ reverse tail i  
 reverse arr 6  

2 comments:

Anonymous said...

Thanks for the great blog. Is there a reason you would not want to implement the list grouping reversion using Seq.take, .skip and .toList?

Thanks.


let rec splitList s i =
if List.length s < i then
[List.rev s]
else
let a = Seq.take i s |> Seq.toList
let b = Seq.skip i s |> Seq.toList
[List.rev a] @ (splitList b i)

splitList l 3

Anonymous said...

Thanks for the great blog. Is there a reason you would not want to implement the list grouping reversion using Seq.take, .skip and .toList?

Thanks.


let rec splitList s i =
if List.length s < i then
[List.rev s]
else
let a = Seq.take i s |> Seq.toList
let b = Seq.skip i s |> Seq.toList
[List.rev a] @ (splitList b i)

splitList l 3

val splitList : s:'a list -> i:int -> 'a list list
val it : int list list = [[3; 2; 1]; [6; 5; 4]; [9; 8; 7]; [11; 10]]