 Explore
Placement Prep Edit Edit

Published on 06 Mar 2020

Reversing a Linked List means reversing the elements of the given Linked List. In this case, let us assume that you are given the pointer to the head node of a linked list. You need to now change the next pointer of every node so that the order of the entire Linked List is reversed. ## Reversing a singly linked list (Iterative approach)

• Initialize pointers prev as NULL, curr as head and next as NULL.
• Iterate through the list. In a loop, do the following.

	    /* Before changing next pointer of current node,
store the next node */
next = curr -> next
/*  Change next pointer of current node */
/* Actual reversing */
curr -> next = prev
/*  Move prev and curr one step ahead */
prev = curr
curr = next


## Iterative C program to reverse a singly linked list

C

Output
Enter the data of node 1: 5
Enter the data of node 2: 10
Enter the data of node 3: 15
Enter the data of node 4: 20

The list is
5 10 15 20

The reversed list is
20 15 10 5

Time Complexity: O(n)
Space Complexity: O(1)


## Reversing a singly linked list (Recursive approach)

1) Break the linked list into two parts - first node and rest of the linked list.

2) Call reverse function for rest of the linked list.

## Recursive C program to reverse a singly linked list

C

Output
NA

Time Complexity: O(n)
Space Complexity: O(1)  