It's easy if you think in terms of pop and push operations. Pop the
first k elements off the head of the list and push them onto a new
list. They're now in reverse order. All that's left is to connect the
two lists. You can do this efficiently if you keep a pointer to the
tail element.
NODE *reverse_k(NODE *lst, int k)
{
NODE *reversed = NULL, *tail = null;
int i;
for (i = 0; i < k; i++) {
// pop the list head
NODE *popped = lst;
lst = lst->next;
// push onto the reversed prefix
popped->next = reversed;
reversed = popped;
// remember the tail of the reversed list
if (tail == NULL) tail = reversed;
}
// glue the rest of the list onto the tail
tail->next = lst;
// the reversed prefix is the new list
return reversed;
}
This is an awkward problem to do with recursion. You will essentially
end up implementing the loop above with tail recursion. In my
opinion, the loop is clearer in this case.
On Aug 5, 3:21 pm, Nikhil Gupta <[email protected]> wrote:
> Sorry. this program reverses the 1st k nodes of the linked list. Not the
> entire list.
>
> On Sat, Aug 6, 2011 at 12:48 AM, Nikhil Gupta
> <[email protected]>wrote:
>
>
>
>
>
> > What is the error in the program? I tried to run it on ideone, but its
> > giving runtime error.
> > This is a program to reverse a linked list.
>
> > #include<stdio.h>
> > #include<malloc.h>
> > int count=0;
> > struct try{
>
> > int data;
> > struct try *next;
> > };
> > typedef struct try node;
> > node *head,*head2;
> > void reverse(node *list, int k)
> > {
> > if(!k)
> > {
> > head=list->next;
> > return;
> > }
> > if(list->next==NULL)
> > return;
> > reverse(list->next,k-1);
> > if(k==1)
> > head2=list->next;
> > list->next->next=list;
>
> > list->next=NULL;
> > }
>
> > void add(node *list,int a)
> > {
> > node *temp;
> > temp=malloc(sizeof(node));
> > temp->data=a;
> > temp->next=NULL;
> > if(list==NULL)
> > list=temp;
> > else
> > {
> > temp->next=list;
> > list=temp;
> > }
> > }
> > void print(node *list)
> > {
> > while(list->next!=NULL)
> > printf("%d",list->data);
> > }
>
> > void del(node *list)
> > {
> > node *temp;
> > while(list!=NULL)
> > {
> > temp=list;
> > free(list);
> > list=temp->next;
> > }
> > }
>
> > int main()
> > {
> > int k;
> > node *list;
> > scanf("%d",&k);
> > list=NULL;
> > add(list,10);
> > add(list,20);
> > add(list,30);
> > add(list,40);
> > add(list,50);
> > add(list,60);
>
> > print(list);
>
> > reverse(list,k-1);
> > list->next=head;
> > print(head2);
> > del(head2);
> > return 0;
> > }
>
> > --
> > Nikhil Gupta
> > Senior Co-ordinator, Publicity
> > CSI, NSIT Students' Branch
> > NSIT, New Delhi, India
>
> --
> Nikhil Gupta
> Senior Co-ordinator, Publicity
> CSI, NSIT Students' Branch
> NSIT, New Delhi, India- Hide quoted text -
>
> - Show quoted text -
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
