# My Weblog

## Reversing the linked list at some given position

Today I got a question to reverse a linked at every kth position. Lets say if we have a linked list
1->2->3->4->5->6->7->8->9->10 and k is 3 then output should be 3->2->1->6->5->4->9->8->7->10. After writing codes in Haskell, getting into pointer stuff mindset is always hard for me. This can be written in 3 lines using Haskell .

```import Data.List

breakList :: ( Show a ) => [ a ] -> Int -> [ a ]
breakList [] _ = []
breakList xs k = reverse p ++ breakList q k  where
( p , q ) = splitAt k xs

*Main> breakList [ 1 , 2, 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 ] 3
[3,2,1,6,5,4,9,8,7,10]
```

Now lets try this one using pointers. In reverse function, we are passing the starting address of every kth element. After reversing the segment, we are calling the reverse function recursively on every segment and copying the starting address of each segment ( prev ) in head->next which is technically after reversing the segment became the end of segment.

```#include<cstdio>
#include<iostream>
using namespace std;

struct node
{
int data;
struct node *next ;
};

struct node *reverse(struct node *head, int k)
{
struct node* prev = NULL;
int count = 0;
//reverse the k nodes of this segment. During the process, prev will point to first node and
while (curr != NULL && count < k )
{
struct node *t  = curr->next;
curr->next = prev;
prev = curr;
curr = t ;
count++;
}

if( curr  !=  NULL)
head->next  = reverse( curr   , k);

return prev;
}

```

Testing code. print and push_back functions are taken from my previous implementation.

```
void print(struct node *curr)
{
while(curr!=NULL) printf("%d -> ",curr->data),curr=curr->next;
printf("\n");
}

void push_back(struct node **ref,int n)
{
struct node *tmp=(struct node*) malloc (sizeof (struct node ));
tmp->data=n;
tmp->next=NULL;
if(*ref==NULL) *ref=tmp;
else
{
struct node *curr=*ref;
while(curr->next!=NULL) curr=curr->next;
curr->next=tmp;
}

}

int main()
{
struct node *q = NULL;
for(int i=1;i<=20;i++)push_back(&q,i);printf("the q list is \n");print(q);
struct node *p = reverse ( q , 4 );
print ( p ) ;
}

Mukeshs-MacBook-Pro:Agda mukeshtiwari\$ ./a.out
the q list is
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 13 -> 14 -> 15 -> 16 -> 17 -> 18 -> 19 -> 20 ->
4 -> 3 -> 2 -> 1 -> 8 -> 7 -> 6 -> 5 -> 12 -> 11 -> 10 -> 9 -> 16 -> 15 -> 14 -> 13 -> 20 -> 19 -> 18 -> 17 ->
```

If you have any suggestions then please let me know.