Reverse A Linked List - InterviewBit

Table Of Contentsshow

• Problem Statement
• Recursive Approach
• Implementation Of Recursive Approach
• C++ Implementation
• Java Implementation
• Python Implementation
• Iterative Approach
• Dry Run of the Iterative Approach
• Implementation of Iterative Approach
• Reverse A Linked List In C++
• Reverse A Linked List In Java
• Reverse A Linked List In Python
• Practice Questions
• Frequently Asked Questions
• Q.1: What is the time complexity of reversing a linked list?
• Q.2: Can we use Stack to reverse the Linked List?
• Q.3: Will the above approaches change the address of the node?
• Additional Resources

Problem Statement

Given a pointer to the head node of a linked list, the task is to reverse the linked list. We need to switch the list by changing the links between nodes.

Example:

• Input: [1,2,3,4,5,NULL]
• Output: [5,4,3,2,1,NULL]
• Explanation:

• Input: [3,4,5]
• Output: [5,4,3]
• Explanation:

Recursive Approach

The recursive approach to reverse a linked list is simple, we have to divide the linked lists into two parts and i.e. first node and the rest of the linked list, and then call the recursion for the other part by maintaining the connection.

Confused about your next job?

In 4 simple steps you can find your personalised career roadmap in Software development for FREE

Expand in New Tab 

Implementation Of Recursive Approach

C++ Implementation

ListNode* reverseList(ListNode* head) { if(!head || !(head->next)) return head; auto res = reverseList(head->next); head->next->next = head; head->next = NULL; return res; }

Java Implementation

static class Node { int data; Node next; Node(int d) { data = d; next = null; } } static Node reverse(Node head) { if (head == null || head.next == null) return head; Node rest = reverse(head.next); head.next.next = head; head.next = null; return rest; }

Python Implementation

def reverse(self, head): # If head is empty or has reached the list end if head is None or head.next is None: return head # Reverse the rest list rest = self.reverse(head.next) # Put first element at the end head.next.next = head head.next = None # Fix the header pointer return rest

• Time complexity: O(N), Where N is the size of the linked list.
• Space complexity: O(1)

Iterative Approach

• We will use 3 variables: prevNode, head, and nextNode.
• prevNode to NULL
• nextNode can stay empty;
• Then we will continue our loop until our current maidenhead pointer is truthy (ie: not NULL), which implies that we reached the end of the linked list
• During our loop, we first of all update nextNode so that it acquires its namesake value, as head->next.
• Finally, we update the head with the value we stored in nextNode.
• And finally, we go on with the loop until we can. After the loop, we return prevNode.

Dry Run of the Iterative Approach

Implementation of Iterative Approach

Reverse A Linked List In C++

ListNode* reverseList(ListNode* head) { ListNode *prev = NULL, *cur=head, *tmp; while(cur){ tmp = cur->next; cur->next = prev; prev = cur; cur = tmp; } return prev; }

Reverse A Linked List In Java

static class Node { int data; Node next; Node(int d) { data = d; next = null; } } /* Function to reverse the linked list */ Node reverse(Node node) { Node prev = null; Node current = node; Node next = null; while (current != null) { next = current.next; current.next = prev; prev = current; current = next; } node = prev; return node; }

Reverse A Linked List In Python

def reverse(self): prev = None current = self.head while (current is not None): next = current.next current.next = prev prev = current current = next self.head = prev

• Time complexity: O(N), Where N is the size of the array.
• Space complexity: O(1)

Practice Questions

• Reverse a Linked List
• Reverse Linked List II

Frequently Asked Questions

Q.1: What is the time complexity of reversing a linked list?

Ans: It is linear in time i.e. O(n) where n is the size of the linked list.

Q.2: Can we use Stack to reverse the Linked List?

Ans: Yes, but the space complexity will increase to O(N).

Q.3: Will the above approaches change the address of the node?

Ans: No, we should try not to change the address of the node.

Additional Resources

• Detect Loop in Linked List
• Add Two Numbers Represented by Linked Lists
• Delete Node in a Linked List
• Intersection of Two Linked Lists
• Linked List Interview Questions
• Linked List MCQ
• Application of Linked List
• Types of Linked List

0 0 5 0 Share 0 Tweet 0 Pin it 5 Share 0