Wap to reverse the first m elements of a linked list of n nodes
Ngày đăng:14/02/2022
Trả lời:65120
Lượt xem:105
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 → NULLN=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 → 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 → NULL
Since the count is 4 now = N thus iteration stops
Final output:4 → 3 → 2 → 1 → 5 → 6 → NULL
ADVERTISEMENT
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 << "\nGiven list\n";
printList(head);
reverseKNodes(&head, k);
cout << "\nModified list\n";
printList(head);
return 0;
}
Java
// Java program for reversal of first k elements
// of given linked list
class Sol
{
// Link list node
static class Node
{
int data;
Node next;
};
// Function to reverse first k elements of linked list
static Node reverseKNodes( Node head_ref, int k)
{
// traverse the linked list until break
// point not meet
Node temp = head_ref;
int count = 1;
while (count < k)
{
temp = temp.next;
count++;
}
// backup the joint point
Node joint_point = temp.next;
temp.next = null; // break the list
// reverse the list till break point
Node prev = null;
Node current = head_ref;
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;
return head_ref;
}
// Function to push a node
static Node push( Node head_ref, int new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.next = (head_ref);
(head_ref) = new_node;
return head_ref;
}
// Function to print linked list
static void printList( Node head)
{
Node temp = head;
while (temp != null)
{
System.out.printf("%d ", temp.data);
temp = temp.next;
}
}
// Driver program to test above function
public static void main(String args[])
{
// Create a linked list 1.2.3.4.5
Node head = null;
head = push(head, 5);
head = push(head, 4);
head = push(head, 3);
head = push(head, 2);
head = push(head, 1);
// k should be less than the
// numbers of nodes
int k = 3;
System.out.print("\nGiven list\n");
printList(head);
head = reverseKNodes(head, k);
System.out.print("\nModified list\n");
printList(head);
}
}
// This code is contributed by Arnab Kundu
Python
# Python program for reversal of first k elements
# of given linked list
# Node of a linked list
class Node:
def __init__(self, next = None, data = None):
self.next = next
self.data = data
# Function to reverse first k elements of linked list
def reverseKNodes(head_ref, k) :
# traverse the linked list until break
# point not meet
temp = head_ref
count = 1
while (count < k):
temp = temp.next
count = count + 1
# backup the joint point
joint_point = temp.next
temp.next = None # break the list
# reverse the list till break point
prev = None
current = head_ref
next = None
while (current != None):
next = current.next
current.next = prev
prev = current
current = next
# join both parts of the linked list
# traverse the list until None is not
# found
head_ref = prev
current = head_ref
while (current.next != None):
current = current.next
# joint both part of the list
current.next = joint_point
return head_ref
# Function to push a node
def push(head_ref, new_data) :
new_node = Node()
new_node.data = new_data
new_node.next = (head_ref)
(head_ref) = new_node
return head_ref
# Function to print linked list
def printList( head) :
temp = head
while (temp != None):
print(temp.data, end = " ")
temp = temp.next
# Driver program to test above function
# Create a linked list 1.2.3.4.5
head = None
head = push(head, 5)
head = push(head, 4)
head = push(head, 3)
head = push(head, 2)
head = push(head, 1)
# k should be less than the
# numbers of nodes
k = 3
print("\nGiven list")
printList(head)
head = reverseKNodes(head, k)
print("\nModified list")
printList(head)
# This code is contributed by Arnab Kundu
C#
// C# program for reversal of first k elements
// of given linked list
using System;
class GFG
{
// Link list node
public class Node
{
public int data;
public Node next;
};
// Function to reverse first k elements of linked list
static Node reverseKNodes(Node head_ref, int k)
{
// traverse the linked list until break
// point not meet
Node temp = head_ref;
int count = 1;
while (count < k)
{
temp = temp.next;
count++;
}
// backup the joint point
Node joint_point = temp.next;
temp.next = null; // break the list
// reverse the list till break point
Node prev = null;
Node current = head_ref;
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;
return head_ref;
}
// Function to push a node
static Node push( Node head_ref, int new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.next = (head_ref);
(head_ref) = new_node;
return head_ref;
}
// Function to print linked list
static void printList( Node head)
{
Node temp = head;
while (temp != null)
{
Console.Write("{0} ", temp.data);
temp = temp.next;
}
}
// Driver Code
public static void Main(String []args)
{
// Create a linked list 1.2.3.4.5
Node head = null;
head = push(head, 5);
head = push(head, 4);
head = push(head, 3);
head = push(head, 2);
head = push(head, 1);
// k should be less than the
// numbers of nodes
int k = 3;
Console.Write("Given list\n");
printList(head);
head = reverseKNodes(head, k);
Console.Write("\nModified list\n");
printList(head);
}
}
// This code is contributed by Princi Singh
Javascript
Output:
Given list
1 2 3 4 5
Modified list
3 2 1 4 5
Time Complexity : O(n)
Article Tags :
Linked List
Reverse
Practice Tags :
Linked List
Reverse
Read Full Article
Reverse a linked list
Given pointer to the head node of a linked list, the task is to reverse the linked list. We need to reverse the list by changing the links between nodes.
Examples:
Input: Head of following linked list 1->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++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include
#include
usingnamespacestd;
// A Linked List Node
structNode
{
intdata;
Node*next;
};
// Utility function to print a linked list
voidprintList(stringmsg,Node*head)
{
cout<<msg;
Node*ptr=head;
while(ptr)
{
cout<<ptr->data<<" —> ";
ptr=ptr->next;
}
cout<<"null"<<endl;
}
// Helper function to insert a new node at the beginning of the linked list
voidpush(Node**head,intdata)
{
Node*newNode=newNode();
newNode->data=data;
newNode->next=*head;
*head=newNode;
}
// Iteratively reverse a linked list from position `m` to `n`
// Note that the head is passed by reference
voidreverse(Node*&head,intm,intn)
{
// base case
if(m>n){
return;
}
Node*prev=NULL;// the previous pointer
Node*curr=head;// the main pointer
// 1. Skip the first `m` nodes
for(inti=1;curr!=NULL&&i<m;i++)
{
prev=curr;
curr=curr->next;
}
// `prev` now points to (m-1)'th node
// `curr` now points to m'th node
Node*start=curr;
Node*end=NULL;
// 2. Traverse and reverse the sublist from position `m` to `n`
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:
Create a new node.
It first checks, whether the head is equal to null which means the list is empty.
If the list is empty, both head and tail will point to the newly added node.
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.
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.
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:
Define a node current which will initially point to the head of the list.
Traverse through the list till current points to null.
Display each node by making current to point to node next to it in each iteration.
Solution
Python
Output:
Original List:
1 2 3 4
Reversed List:
4 3 2 1
Output:
Original List:
1 2 3 4
Reversed List:
4 3 2 1
JAVA
Output:
Original List:
1 2 3 4
Reversed List:
4 3 2 1
C#
Output:
Original List:
1 2 3 4
Reversed List:
4 3 2 1
PHP
Output:
Original List:
1 2 3 4
Reversed List:
4 3 2 1
Reverse a Linked List from position m to n-Interview Problem
Difficulty: Medium
Asked in: Amazon, Facebook, Microsoft
Understanding the problem
Problem Description: Given a head pointer of a Linked List and two positions say m and n, you have to reverse the given Linked List only from position m to position n. Then, return the head of the m to n reversed Linked List.
For Example:
Input: 15->20->25->30->35->NULL, m = 2 and n = 4
Output: 15->30->25->20->35->NULL
Input: 20->40->60->70->NULL, m = 2 and n = 3
Output: 20->60->40->70->NULL
Possible follow-up questions to ask: →
Is the value of m and n always different? (Ans: No, it can be same too)
Node Structure of the Linked List:
class ListNode
{
int data
ListNode next
}
Solution
Solution idea
Since we have to reverse a part of the given linked list obviously we need the concept of reversing the linked list. We need to find the mth node and pass it to the reverse function (which will reverse the given part). But, before passing the mth node we need to traverse to the nth node and cut its link with (n+1)th node if present.
Also we have to save the the (m-1) node and also (n+1)th node address so that we can link the reversed part of the linked list again with the original linked list.
Solution steps
We will use following four variable:
1. revPrev → for storing the previous node, i.e. (m-1)th node.
2. revStart → for storing the starting(mth) node of reversal.
3. revEnd → for storing the ending node(nth) of reversal.
4. revNext → for storing the next node, i.e. (n+1)th node.
Now, we will pass revStart to the reverse function and then will attach the reversed part with revStart and revEnd to get the reversed linked list.
Time Complexity: O(L), where L is the length of the linked list.
Space Complexity: O(1)
Critical ideas to think
Can you implement the reverse function using iteration?
Can you think of reversing a linked list using a stack?
Can we reverse a linked list in less than O(n) time? What if it is a doubly linked list?
Suggested Problems to Solve
Reverse even elements in a Linked List
Reverse a Doubly Linked List
Reverse last K elements of a Linked List
Reverse a Linked List in groups of given size
Happing Coding! Enjoy Algorithms!!
AfterAcademy Data Structure And Algorithms Online Course — Admissions Open
Required knowledge
Basic C programming, Functions, Singly Linked List, Dynamic memory allocation
Algorithm to reverse a Singly Linked List
Algorithm to reverse a Singly Linked List%%Input : head node of the linked list
Begin:If (head != NULL) then
prevNode ← head
head ← head.next
curNode ← head
prevNode.next ← NULLWhile (head != NULL) do
head ← head.next
curNode.next ← prevNode
prevNode ← curNode
curNode ← head
End while
head ← prevNode
End ifEnd
Python Program to Reverse only First N Elements of a Linked List
PythonServer Side ProgrammingProgramming
When it is required to reverse a specific set of elements in a linked list, a method named ‘reverse_list’ is defined. This iterates through the list, and reverses the specific set of elements.
