Explore
ProGrad Programs
Placement Prep
TCS Codevita
Webinars
About Us

Edit
Reply




Edit

Reversing a Linked List | Operation on Linked List

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 linked list

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.

3) Link rest and first.

4) Change the head pointer.

 

Recursive C program to reverse a singly linked list


C

Output
NA


Time Complexity: O(n)
Space Complexity: O(1)
If you have any feedback about this article and want to improve this, please write to enquiry@faceprep.in
Explore 'quantitative aptitude'
Articles Practice Exercises