# C program to Reverse only First N Elements of a Linked List

**Display a linked list in reverse**: Here, we are going to implement a **C program to display the linked list in reverse using recursion**.

Submitted by Radib Kar, on December 26, 2018

**Problem statement: Given a linked list reverse it up to first N elements without using any additional space.**

**Example:**

N= 4 The linked list is: 1 → 2 → 3 → 4 → 5 → 6 → NULL So the output will be 4 → 3 → 2 → 1 → 5 → 6

**Solution:**

**Reversing a single linked list up to first N elements** is about reversing the linking direction. We can solve the above problem by following steps:

**Building the linked list**

Build the linked list by appending each node at the end. (For details refer to: Single linked list insertion)-
**Function to reverse the link list**

As told previously, the basic idea to reverse a linked list is to reverse the direction of linking for the First N elements. This concept can be implemented without using any additional space. We need three pointers *prev, *cur, *next to implement the function. These variables are named accordingly to indicate their serving part in the function.

*prev - to store the previous node which will become ultimately the next node after reversal for current node

*cur - to store the current node

*next - to store the next node which will become current node in the next iteration.

First traverse to the node that don't need to be reversed (n+1 th), store its address to temp

Initialize *prev to temp & *next to NULL, *cur to head

Initialize count to 0 which stores the number of elements to be reversedWhile(cur!=NULL&& count<N) Set *next to cur->next Set cur->next to *prev Set *prev to *cur Set *cur to *next End While loop

Set head to *prev - Print the reversed linked list

**Example: **

Let the linked list be1 → 2 → 3 → 4 → 5 → 6 → NULLN=4(for simplicity in understanding representing pointer to node by node value) Head is 1Initialize:cur =1, prev=5 ( from 5 no reversal needed) next=NULL count=0in iteration 1:next=2 cur->next=5 prev=1 cur=2 count is 1 thus reversed part:1 → 5 → 6 → NULLin iteration 2:next=3 cur->next=1 prev=2 cur=3 count is 2 thus reversed part:2 → 1 → 5 → 6 → NULLin iteration 3:next=4 cur->next=2 prev=3 cur=4 count is 3 thus reversed part:3 → 2 → 1 → 5 → 6 → NULLin iteration 4:next=5 cur->next=3 prev=4 cur=5 count is 4 thus reversed part:4 → 3 → 2 → 1 → 5 → 6 → NULLSince the count is 4 now = N thus iteration stopsFinal output:4 → 3 → 2 → 1 → 5 → 6 → NULL

## C implementation to Reverse only First N Elements of a Linked List

#include <stdio.h> #include <stdlib.h> struct node{ int data; // data field struct node *next; }; void display(struct node* head){ struct node* current=head; // current node set to head printf("traversing the list...\n"); while(current!=NULL){ //traverse until current node isn't NULL printf("%d ",current->data); current=current->next; // go to next node } } struct node* reverse_N(struct node* head,struct node* temp,int n){ struct node *next=NULL,*cur=head,*prev=temp; //initialize the pointers int count=0; while(cur!=NULL && (count++)<n){//loop till the end of linked list next=cur->next;//next = cur->next to store the rest of the list; cur->next=prev;//change the direction of linked list prev=cur; //update prev cur=next; //update cur } head=prev; //update head return head; //return head } struct node* creatnode(int d){ struct node* temp=malloc(sizeof(struct node)); temp->data=d; temp->next=NULL; return temp; } int main(){ printf("creating the linked list by inserting new nodes at the end\n"); printf("enter 0 to stop building the list, else enter any integer\n"); int k,count=0,x=1,n; struct node* curr,*temp; scanf("%d",&k); struct node* head=creatnode(k); //buliding list, first node scanf("%d",&k); temp=head; ///////////////////inserting at the end////////////////////// while(k){ curr=creatnode(k); temp->next=curr;//appending each node temp=temp->next; x++; scanf("%d",&k); } display(head); // displaying the list printf("\nInput N\n"); while(1){ scanf("%d",&n); if(n<x) break; printf("N greater than no of element, enter again\n"); } printf("\nreversing upto first N elements...\n"); //traversing to the node from which no reversing needed temp=head; while((count++)<n){ temp=temp->next; } head=reverse_N(head,temp,n); display(head); // displaying the reversed( only first N terms) list return 0; }

**Output**

First run: creating the linked list by inserting new nodes at the end enter 0 to stop building the list, else enter any integer 1 2 3 4 5 6 0 traversing the list... 1 2 3 4 5 6 Input N 4 reversing upto first N elements... traversing the list... 4 3 2 1 5 6 Second run: creating the linked list by inserting new nodes at the end enter 0 to stop building the list, else enter any integer 5 7 8 -5 -6 9 7 -6 0 traversing the list... 5 7 8 -5 -6 9 7 -6 Input N 9 N greater than no of element, enter again 6 reversing upto first N elements... traversing the list... 9 -6 -5 8 7 5 7 -6

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.

Learn PCB Designing: PCB DESIGNING TUTORIAL