Top List List

Wap to reverse the first m elements of a linked list of n nodes

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&& countnext 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 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

Reverse first K elements of given linked list

Given a pointer to the head node of a linked list and a number K, the task is to reverse the first K nodes of the linked list. We need to reverse the list by changing links between nodes.
check also Reversal of a linked list

Examples:

Input : 1->2->3->4->5->6->7->8->9->10->NULL k = 3 Output :3->2->1->4->5->6->7->8->9->10->NULL Input :10->18->20->25->35->NULL k = 2 Output :18->10->20->25->35->NULL

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Explanation of the method:
suppose linked list is 1->2->3->4->5->NULL and k=3
1] Traverse the linked list till K-th point.
2] Break the linked list in to two parts from k-th point. After partition linked list will look like 1->2->3->NULL & 4->5->NULL
3] Reverse first part of the linked list leave second part as it is 3->2->1->NULL and 4->5->NULL
4] Join both the parts of the linked list, we get 3->2->1->4->5->NULL
A pictorial representation of how the algorithm works

C++

// C++ program for reversal of first k elements

// of given linked list

#include

using namespace std;

/* Link list node */

struct Node {

int data;

struct Node* next;

};

/* Function to reverse first k elements of linked list */

static void reverseKNodes[struct Node** head_ref, int k]

{

// traverse the linked list until break

// point not meet

struct Node* temp = *head_ref;

int count = 1;

while [count < k] {

temp = temp->next;

count++;

}

// backup the joint point

struct Node* joint_point = temp->next;

temp->next = NULL; // break the list

// reverse the list till break point

struct Node* prev = NULL;

struct Node* current = *head_ref;

struct Node* next;

while [current != NULL] {

next = current->next;

current->next = prev;

prev = current;

current = next;

}

// join both parts of the linked list

// traverse the list until NULL is not

// found

*head_ref = prev;

current = *head_ref;

while [current->next != NULL]

current = current->next;

// joint both part of the list

current->next = joint_point;

}

/* Function to push a node */

void push[struct Node** head_ref, int new_data]

{

struct Node* new_node =

[struct Node*]malloc[sizeof[struct Node]];

new_node->data = new_data;

new_node->next = [*head_ref];

[*head_ref] = new_node;

}

/* Function to print linked list */

void printList[struct Node* head]

{

struct Node* temp = head;

while [temp != NULL] {

printf["%d ", temp->data];

temp = temp->next;

}

/* Driver program to test above function*/

int main[]

{

// Create a linked list 1->2->3->4->5

struct Node* head = NULL;

push[&head, 5];

push[&head, 4];

push[&head, 3];

push[&head, 2];

push[&head, 1];

// k should be less than the

// numbers of nodes

int k = 3;

cout 2->3->4->NULL
Output: Linked list should be changed to,
4->3->2->1->NULL

Input: Head of following linked list
1->2->3->4->5->NULL
Output: Linked list should be changed to,
5->4->3->2->1->NULL

Input: NULL
Output: NULL

Input: 1->NULL
Output: 1->NULL

C++

100

101

102

103

104

105

106

107

108

109

110

111

#include

using namespace std;

// A Linked List Node

struct Node

{

int data;

Node* next;

};

// Utility function to print a linked list

void printList[string msg, Node* head]

{

cout next = end;

end = curr;

// move to the next node

curr = next;

}

`start` points to the m'th node

`end` now points to the n'th node

`curr` now points to the [n+1]'th node

// 3. Fix the pointers and return the head node

if [start]

{

start->next = curr;

if [prev != NULL] {

prev->next = end;

}

// when m = 1, `prev` is nullptr

else {

// fix the head pointer to point to the new front

head = end;

}

int main[]

{

int m = 2, n = 5;

Node* head = NULL;

for [int i = 7; i >= 1; i--] {

push[&head, i];

}

printList["Original linked list: ", head];

reverse[head, m, n];

printList["Reversed linked list: ", head];

return 0;

}

DownloadRun Code

Output:

Original linked list: 1 —> 2 —> 3 —> 4 —> 5 —> 6 —> 7 —> null
Reversed linked list: 1 —> 5 —> 4 —> 3 —> 2 —> 6 —> 7 —> null

Program to create a singly linked list of n nodes and display it in reverse order

Explanation

In this program, we need to create a singly linked list and display the list in reverse order.

Original List

Reversed List

One of the approaches to solving this problem is to reach the end the of the list and display the nodes from tail to head recursively.

Algorithm

Create a class Node which has two attributes: data and next. Next is a pointer to the next node in the list.
Create another class which has two attributes: head and tail.
addNode[] will add a new node to the list:
1. Create a new node.
2. It first checks, whether the head is equal to null which means the list is empty.
3. If the list is empty, both head and tail will point to the newly added node.
4. If the list is not empty, the new node will be added to end of the list such that tail's next will point to the newly added node. This new node will become the new tail of the list.
reverse[] will reverse the order of the nodes present in the list.
1. This method checks whether node next to current is null which implies that, current is pointing to tail, then it will print the data of the tail node.
2. Recursively call reverse[] by considering node next to current node and prints out all the nodes in reverse order starting from the tail.
display[] will display the nodes present in the list:
1. Define a node current which will initially point to the head of the list.
2. Traverse through the list till current points to null.
3. Display each node by making current to point to node next to it in each iteration.