   # 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
252 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
Share this question

## 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
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).