CODEWITHSUNDEEP
c++linked-list
Naveen Kumar
Naveen Kumar

Reputation: 424

C++ program to Reverse a linked list from position m to n

I am stuck on this simple question for hours...can someone plz help...where i am going wrong?

Question : Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example: Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note: 1 ≤ m ≤ n ≤ length of list

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;

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

node *newNode(int key)
{
    node *temp = new node;
    temp->data = key;
    temp->next = NULL;
    return temp;
}

ListNode* reverseUpto(ListNode *head, int size)
{
    if(size<=1)
        return head;
    ListNode *cur=head,*newhead=NULL,*temp;
    for(int i=0;i<size;i++)
    {
        temp=cur;
        cur=cur->next;
        temp->next=newhead;
        newhead=temp;
    }
    head->next=cur;
    return newhead;
}

ListNode* reverseBetween(ListNode* A, int m, int n)
{
    ListNode *head=A;
    if(m==n)
        return A;
    ListNode *dummyhead=newNode(0);
    dummyhead->next=head;
    ListNode *prev=dummyhead;
    ListNode *cur=head;
    int counter=1;
    while(counter<m)
    {
        printf("counter= %d     prev=%d     cur=%d\n",counter,prev->data,cur->data);
        counter++;
        prev=cur;
        cur=cur->next;
    }
    prev->next=NULL;
    ListNode * retPtr=reverseUpto(cur,m-n+1);
    prev->next=retPtr;
    return A;
}

void printlist(node *head)
{
    while(head != NULL)
    {
        cout << head->data << " ";
        head = head->next;
    }
    cout << endl;
}

int main()
{
    node *head1 = newNode(1);
    head1->next = newNode(2);
    head1->next->next = newNode(3);
    head1->next->next->next = newNode(4);
    head1->next->next->next->next = newNode(5);
    head1->next->next->next->next->next = newNode(6);
    head1->next->next->next->next->next->next = newNode(7);
    head1->next->next->next->next->next->next->next = newNode(8);
    cout << "Given linked list\n";
    printlist(head1);
    head1=reverseBetween(head1,3,5);
    cout << "\nReversed linked list\n";
    printlist(head1);
    return 0;
}

I am getting same output as my input!!....where is the pitfall?

Upvotes: 1

Views: 1670

Answers (1)

Junius li
Junius li

Reputation: 32

ListNode * retPtr=reverseUpto(cur,m-n+1);

modify to 

ListNode * retPtr=reverseUpto(cur,n-m+1);

Upvotes: 2

Related Questions