top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

Input List => 1 2 3 4 5 6 7 8 9 10 11 Output List => 3 2 1 6 5 4 9 8 7 10 11

+4 votes
654 views

Can someone please write a C program to reverse "N" nodes of list. In the above question N= 3.
Program should be generic so it can work for any value assigned to N.

Input List => 1 2 3 4 5 6 7 8 9 10 11
Output List => 3 2 1 6 5 4 9 8 7 10 11
for N=3

Input List => 1 2 3 4 5 6 7 8 9 10 11
Output List => 4 3 2 1 8 7 6 5 9 10 11
for n=4

posted Oct 10, 2013 by Neeraj Mishra

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

2 Answers

+6 votes
struct node * reverse_num_node (struct node *beg, struct node **next_head, int N)
{
    struct node *prev = beg; int n = 1;
    struct node *current = prev->next;
    struct node *next;

    if (beg == NULL)
        return NULL;

    while (current && ( N > n))
    {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
        n++;
    }
    if (!current && (n < N))
    {
         beg = reverse_num_node (prev, next_head, n);
         prev->next = NULL;
         return beg;
    }
    *next_head = current;
    return prev;
}

struct node * reverse_list_node (struct node * head, int N)
{
    struct node *beg = head;
    struct node *next_head = NULL;
    struct node *tmp = beg;

    if(head = reverse_num_node (beg, &next_head, N))
    {
        beg = next_head;
        while(next_head)
        {
            tmp->next = reverse_num_node (beg, &next_head, N);
            tmp = beg;
            beg = next_head;
        }
        tmp->next = next_head;
    }
    return head;
}

Complexity
n => Total no of node in list.
N => No of node need to reverse.

Best case O(n). When "n" is multiple of N.
Worst Case O(n + N -1) When "n" is one less than multiple of N.

answer Oct 10, 2013 by Vikas Upadhyay
0 votes
struct Node *NplusOnethNode(struct Node *head, int n)
{
         struct Node *nth_node;
          int p;
          if(head == NULL)
                 return head;
           for(p=0; nth_node = head &&(i<n); i++, nth_node = nth_node->next);
           if((p==n)&&(nth_node!= NULL))
                {
                      return nth_node;
                }
             return head->next;
}

int ContainsNnodes(struct Node *head, int n)
{
          int i;
          for(i=0; head &&(i<n); i++, head = head->next);
          if(i==n)
             return i;
           return 0;
}

struct Node *reverseNnodes(struct Node *head, int n)
{
       struct Node *nptr= head, *temp, *next, nexthead;
        int i;
        if(n==0 || n== 1)
         return head;
       if(ContainsNnodes(nptr, n-1))
           nexthead = NplusOnethNode(nptr, n-1);
        else 
           nexthead = head;
        while( nptr && ContainsNnodes(nptr, n))
         {
               temp =  NplusOnethNode(nptr, n);
               i =0;
               while(i<n)
                {
                    next = nptr->next;
                    nptr->next =  temp;
                    temp = nptr;
                    nptr = next;
                    i++;
                  }
         }
         return nexthead;
}
answer Oct 10, 2013 by anonymous
Can you please explain the complexity of code.

As per my understanding complexity of your code is O(n2).
Similar Questions
+2 votes

How PCEF decide which QCI_X(where X = 1,2,3,4,5,6,7,8,9,65,66,67,68,69,70) value need to be send to PCRF.
What is the significance of so many QOS-Class-Identifiers?
Even 3GPP 29.212 doesn't define any reason for classification between different QOS-Class-Identifiers.

+4 votes

Calculate 1+2+…+n without multiplication, division, key words for, while, if, else, switch, case, as well as conditional operator (A ? B : C).

...