1

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?

4
  • 4
    codereview.stackexchange.com/questions/106811/… Commented May 21, 2016 at 8:41
  • What is your specific question ? Please read: How to Ask Commented May 21, 2016 at 8:47
  • My question is where is the pitfall in my solution? I am getting same output as my input! Commented May 21, 2016 at 8:53
  • your code is impossible to read towards end such as node *head1 = newNode(1); head1->next = newNode(2); instead why dont you write head *head1 = newNode(1); node* node2= newNode(2); head->next=node2 I am sure then it will be easier to read and debug Commented May 21, 2016 at 8:59

1 Answer 1

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

modify to

ListNode * retPtr=reverseUpto(cur,n-m+1);
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.