  Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email  Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

Last Updated on March 30, 2022 by Ria Pathak Easy.

### Problem Statement :

See original problem statement here

#### Example:

``````Assume that we have linked list 1 → 2 → 3 → Ø,
we have to change it to Ø ← 1 ← 2 ← 3.``````

### Explanation:

#### Approach 1(Iterative approach):

While you are traversing the list, change the current node’s next pointer to point to its previous element. Since a node does not have reference to its previous node, you must store its previous element beforehand. You also need another pointer to store the next node before changing the reference. Do not forget to return the new head reference at the end! ```struct Node* Reverse(Node *head)
{
Node *tail, *t;
tail = NULL;
{
}
return tail;
// Complete this method
}
```
``` public static Node reverseLinkedList(Node currentNode)
{
// For first node, previousNode will be null
Node previousNode=null;
Node nextNode;
while(currentNode!=null)
{
nextNode=currentNode.next;
currentNode.next=previousNode;
// moving currentNode and previousNode by 1 node
previousNode=currentNode;
currentNode=nextNode;
}
return previousNode;
}
```
```def Reverse(head):

tail = NULL

return tail

```

#### Approach 2(Using recursion):

We can find it easier to start from the bottom up,by asking and answering tiny questions:

1. What is the reverse of NULL? NULL.

2. What is the reverse of a one element list?The element itself.

3. What is the reverse of an n element list? The reverse of the second element followed by the first element.

### Refer to commented implementation

``````     Node Reverse(Node head) {

/* We have two conditions in this if statement.
This first condition immediately returns null
when the list is null. The second condition returns
the final node in the list. That final node is sent
into the "remaining" Node below.
-----------------------------------------------------*/

}

/* When the recursion creates the stack for A -> B -> C
(RevA(RevB(RevC()))) it will stop at the last node and
the recursion will end, beginning the unraveling of the
nested functions from the inside, out.
-----------------------------------------------------*/

/* Now we have the "remaining" node returned and accessible
to the node prior. This remaining node will be returned
by each function as the recursive stack unravels.

and B is after A, (A -> B), would set B's pointer to A,
reversing their direction to be A <- B.
-----------------------------------------------------*/

/* Now that those two elements are reversed, we need to set
the pointer of the new tail-node to null.
-----------------------------------------------------*/

/* Now we return remaining so that remaining is always
reassigned to itself and is eventually returned by the
first function call.
-----------------------------------------------------*/

return remaining;
}``````

### SOLUTION:

```#include <stdio.h>
#include <stdlib.h>

/* A structure of linked list node */
struct node {
int data;
struct node *next;

void initialize(){
}

/*
Given a Inserts a node in front of a singly linked list.
*/
void insert(int num) {
/* Create a new Linked List node */
struct node* newNode = (struct node*) malloc(sizeof(struct node));
newNode->data  = num;
/* Next pointer of new node will point to head node of linked list  */
printf("Inserted Element : %d\n", num);
}

/* Reverses a Linked List using recursion */
void reverse(struct node* nodePtr) {

/* empty list */
if (nodePtr == NULL)
return;
/* Last node (tail node)*/
if(nodePtr->next == NULL){
return;
}

/* reverse the rest of list and put the first element at the end */
reverse(nodePtr->next);
nodePtr->next->next = nodePtr;
nodePtr->next = NULL;
}

/*
*/
while (nodePtr != NULL) {
printf("%d", nodePtr->data);
nodePtr = nodePtr->next;
if(nodePtr != NULL)
printf("-->");
}
}

int main() {
initialize();
insert(1);
insert(2);
insert(3);
insert(4);
insert(5);

return 0;
}
```
``` #include <bits stdc++.h="">
using namespace std;
struct node{
int data;
node* next;
};
node* newnode(int x)
{
node* temp=new node();
temp->data=x;
temp->next=NULL;
return temp;
}
{
return restlist;
}
int main()
{
int t;cin>>t;
while(t--)
{
int n;
cin>>n;
int x;cin>>x;
node* temp=newnode(x);
for(int i=1;i<n;i++) {="" int="" x;cin="">>x;
}
{
}
cout<<"\n";
}
return 0;
}
```
```import java.io.*;
import java.util.*;
public class Main{
public int data;
this.data = nodeData;
this.next = null;
}
}

this.tail = null;
}

public void insertNode(int nodeData) {

} else {
this.tail.next = node;
}

this.tail = node;
}
}
{
while(temp!=null)
{
System.out.print(temp.data+" ");
temp=temp.next;
}
System.out.println();
}
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}

}

private static final Scanner scanner = new Scanner(System.in);

public static void main(String[] args) throws IOException {
int testCases = scanner.nextInt();

while (testCases-- > 0) {

int llistCount = scanner.nextInt();

for (int i = 0; i < llistCount; i++) {
int llistItem = scanner.nextInt();

llist.insertNode(llistItem);
}

}

scanner.close();
}
}
```
```class node:
def __init__(self):
self.data = None
self.next = None

def newnode(x):

temp= node()
temp.data = x
temp.next = None
return temp

return restlist

for _ in range(int(input())):

n = int(input())
a = list(map(int,input().split()))
temp = newnode(a)

for i in range(1, n):