Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Last Updated: 4 Dec, 2020

Easy

```
Input:
2 4 5 -1
Output:
5 4 2 -1
Explanation: 2->4->5 is the initial linked list. If we reverse this, we get 5->4->2.
```

```
The first line contains the elements of the singly linked list separated by a single space and terminated by -1. Hence, -1 would never be a list element.
```

```
Print the reversed linked list. The elements of the reversed list should be single-space separated, terminated by -1.
```

```
You do not need to print anything, just return the head of the reversed linked list.
```

One way is to use recursion to reverse the list. Divide the linked list in two halves, the first node and the rest of the list. Reverse the second half using recursion and append the first half, that is the first node at the end of the reversed linked list. Return the head of the reversed linked list.

- If the list contains only one node, return the head of the list.
- Else, divide the list into two parts, first node and the rest of the linked list.
- Call the reverse for the rest of the linked list.
- Append the first node at the end of the reversed linked list, the linked list obtained in step 2.
- Return the head of the reversed linked list, obtained in step 4.

Reverse the link of each node, starting from the head and moving towards the tail of the linked list. Take three-pointers, ‘curr’, ‘ahead’, ‘prev’. Initialize curr with the head node, ahead, and prev with NULL. Keep on iterating the linked list until ‘curr’ reaches NULL. Store the next node of the current node in ‘ahead’ before changing the next of the current node and point the next of the current node to ‘prev’ (pointer to the node just before the current node). This is the actual reversing of the links in the linked list. Point ‘prev’ node to ‘curr’ node and ‘curr’ node to ‘ahead’ node. At the end return the head of the reversed linked list.

- Initialize three pointers prev as NULL, curr as head and ahead as NULL.
- Iterate through the linked list and do following

a. Point ‘ahead’ to the next of the current node, ahead = curr->next

b. Point next of the curr node to ‘prev’, curr->next = prev.

c. Point the prev node to the curr node and curr node to the ‘ahead’ node. - Return ‘prev’ , as it will be the head of the reversed linked list and ‘curr’ will be pointing to NULL at this point.

Similar problems

Deletion In Doubly Linked List

Easy

Posted: 22 Apr, 2022

Deletion In Doubly Linked List

Easy

Posted: 22 Apr, 2022

Insertion In Doubly Linked List

Easy

Posted: 24 Apr, 2022

Insertion In Doubly Linked List

Easy

Posted: 24 Apr, 2022

LRU Cache

Moderate

Posted: 10 Sep, 2022

Delete Nodes On Regular Intervals

Ninja

Posted: 19 Dec, 2022

Add One To Linked List

Hard

Posted: 19 Dec, 2022