Home » C/C++ Data Structure Programs

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

In this tutorial, we will learn how to reverse only the first N elements of a linked list using a C++ program? By Radib Kar Last updated : August 01, 2023

Problem Statement

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

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

Reversing a single linked list up to first N elements

To reverse a single linked list up to first N elements, you can use the following steps:

1. Building the linked list
   Build the linked list by appending each node at the end. (For details refer to: Single linked list insertion)
2. 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 reversed

   While(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
3. Print the reversed linked list

Example with explanation

Let the linked list be 1 → 2 → 3 → 4 → 5 → 6 → NULL
N=4
(for simplicity in understanding representing 
pointer to node by node value)
Head is 1

Initialize:
cur =1, prev=5 ( from 5 no reversal needed)
next=NULL
count=0

in iteration 1:
next=2
cur->next=5
prev=1
cur=2
count is 1
thus reversed part: 1 → 5 → 6 → NULL

in iteration 2:
next=3
cur->next=1
prev=2
cur=3
count is 2
thus reversed part: 2 → 1 → 5 → 6 → NULL

in iteration 3:
next=4
cur->next=2
prev=3
cur=4
count is 3
thus reversed part: 3 → 2 → 1 → 5 → 6 → NULL

in iteration 4:
next=5
cur->next=3
prev=4
cur=5
count is 4
thus reversed part: 4 → 3 → 2 → 1 → 5 → 6 → NULL

Since the count is 4 now = N thus iteration stops

Final output:
4 → 3 → 2 → 1 → 5 → 6 → NULL

C program 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