How many pointers do you need to reverse a linked list?

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

Examples:

Input: Head of following linked list
1->2->3->4->NULL
Output: Linked list should be changed to,
4->3->2->1->NULL

Input: Head of following linked list
1->2->3->4->5->NULL
Output: Linked list should be changed to,
5->4->3->2->1->NULL

Input: NULL
Output: NULL

Input: 1->NULL
Output: 1->NULL

Iteratively Reverse a linked list using only 2 pointers (An Interesting Method)

Given pointer to the head node of a linked list, the task is to reverse the linked list.

Examples:

Input : Head of following linked list 1->2->3->4->NULL Output : Linked list should be changed to, 4->3->2->1->NULL Input : Head of following linked list 1->2->3->4->5->NULL Output : Linked list should be changed to, 5->4->3->2->1->NULL

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

We have seen how to reverse a linked list in article Reverse a linked list. In iterative method we had used 3 pointers prev, cur and next. Below is an interesting approach that uses only two pointers. The idea is to use XOR to swap pointers.

C++

// C++ program to reverse a linked list using two pointers. #include <bits/stdc++.h> using namespace std; typedef uintptr_t ut; /* Link list node */ struct Node { int data; struct Node* next; }; /* Function to reverse the linked list using 2 pointers */ void reverse(struct Node** head_ref) { struct Node* prev = NULL; struct Node* current = *head_ref; // at last prev points to new head while (current != NULL) { // This expression evaluates from left to right // current->next = prev, changes the link from // next to prev node // prev = current, moves prev to current node for // next reversal of node // This example of list will clear it more 1->2->3->4 // initially prev = 1, current = 2 // Final expression will be current = 1^2^3^2^1, // as we know that bitwise XOR of two same // numbers will always be 0 i.e; 1^1 = 2^2 = 0 // After the evaluation of expression current = 3 that // means it has been moved by one node from its // previous position current = (struct Node*)((ut)prev ^ (ut)current ^ (ut)(current->next) ^ (ut)(current->next = prev) ^ (ut)(prev = current)); } *head_ref = prev; } /* Function to push a node */ void push(struct Node** head_ref, int new_data) { /* allocate node */ struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); /* put in the data */ new_node->data = new_data; /* link the old list off the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node; } /* Function to print linked list */ void printList(struct Node* head) { struct Node* temp = head; while (temp != NULL) { printf("%d ", temp->data); temp = temp->next; } } /* Driver program to test above function*/ int main() { /* Start with the empty list */ struct Node* head = NULL; push(&head, 20); push(&head, 4); push(&head, 15); push(&head, 85); printf("Given linked list\n"); printList(head); reverse(&head); printf("\nReversed Linked list \n"); printList(head); return 0; }

Java

// Java program to reverse a linked // list using two pointers. import java.util.*; class Main{ // Link list node static class Node { int data; Node next; }; static Node head_ref = null; // Function to reverse the linked // list using 2 pointers static void reverse() { Node prev = null; Node current = head_ref; // At last prev points to new head while (current != null) { // This expression evaluates from left to right // current.next = prev, changes the link from // next to prev node // prev = current, moves prev to current node for // next reversal of node // This example of list will clear it more 1.2.3.4 // initially prev = 1, current = 2 // Final expression will be current = 1^2^3^2^1, // as we know that bitwise XOR of two same // numbers will always be 0 i.e; 1^1 = 2^2 = 0 // After the evaluation of expression current = 3 that // means it has been moved by one node from its // previous position Node next = current.next; current.next = prev; prev = current; current = next; } head_ref = prev; } // Function to push a node static void push(int new_data) { // Allocate node Node new_node = new Node(); // Put in the data new_node.data = new_data; // Link the old list off the new node new_node.next = (head_ref); // Move the head to point to the new node (head_ref) = new_node; } // Function to print linked list static void printList() { Node temp = head_ref; while (temp != null) { System.out.print(temp.data + " "); temp = temp.next; } } // Driver code public static void main(String []args) { push(20); push(4); push(15); push(85); System.out.print("Given linked list\n"); printList(); reverse(); System.out.print("\nReversed Linked list \n"); printList(); } } // This code is contributed by rutvik_56

Python3

# Iteratively Reverse a linked list using only 2 pointers (An Interesting Method) # Python program to reverse a linked list # Link list node # node class class node: # Constructor to initialize the node object def __init__(self, data): self.data = data self.next = None class LinkedList: # Function to initialize head def __init__(self): self.head = None # Function to reverse the linked list def reverse(self): prev = None current = self.head # Described here https://www.geeksforgeeks.org/ # how-to-swap-two-variables-in-one-line / while(current is not None): # This expression evaluates from left to right # current->next = prev, changes the link from # next to prev node # prev = current, moves prev to current node for # next reversal of node # This example of list will clear it more 1->2 # initially prev = 1, current = 2 # Final expression will be current = 1, prev = 2 next, current.next = current.next, prev prev, current = current, next self.head = prev # Function to push a new node def push(self, new_data): # allocate node and put in the data new_node = node(new_data) # link the old list off the new node new_node.next = self.head # move the head to point to the new node self.head = new_node # Function to print the linked list def printList(self): temp = self.head while(temp): print (temp.data,end=" ") temp = temp.next # Driver program to test above functions llist = LinkedList() llist.push(20) llist.push(4) llist.push(15) llist.push(85) print ("Given Linked List") llist.printList() llist.reverse() print ("\nReversed Linked List") llist.printList() # This code is contributed by Afzal Ansari

C#

// C# program to reverse a linked // list using two pointers. using System; using System.Collections; using System.Collections.Generic; class GFG { // Link list node class Node { public int data; public Node next; }; static Node head_ref = null; // Function to reverse the linked // list using 2 pointers static void reverse() { Node prev = null; Node current = head_ref; // At last prev points to new head while (current != null) { // This expression evaluates from left to right // current.next = prev, changes the link from // next to prev node // prev = current, moves prev to current node for // next reversal of node // This example of list will clear it more 1.2.3.4 // initially prev = 1, current = 2 // Final expression will be current = 1^2^3^2^1, // as we know that bitwise XOR of two same // numbers will always be 0 i.e; 1^1 = 2^2 = 0 // After the evaluation of expression current = 3 that // means it has been moved by one node from its // previous position Node next = current.next; current.next = prev; prev = current; current = next; } head_ref = prev; } // Function to push a node static void push(int new_data) { // Allocate node Node new_node = new Node(); // Put in the data new_node.data = new_data; // Link the old list off the new node new_node.next = (head_ref); // Move the head to point to the new node (head_ref) = new_node; } // Function to print linked list static void printList() { Node temp = head_ref; while (temp != null) { Console.Write(temp.data + " "); temp = temp.next; } } // Driver code public static void Main(string []args) { push(20); push(4); push(15); push(85); Console.Write("Given linked list\n"); printList(); reverse(); Console.Write("\nReversed Linked list \n"); printList(); } } // This code is contributed by pratham76

Javascript

<script> // javascript program to reverse a linked // list using two pointers. // Link list node class Node { constructor() { this.data = 0; this.next = null; } } var head_ref = null; // Function to reverse the linked // list using 2 pointers function reverse() { var prev = null; var current = head_ref; // At last prev points to new head while (current != null) { // This expression evaluates from left to right // current.next = prev, changes the link from // next to prev node // prev = current, moves prev to current node for // next reversal of node // This example of list will clear it more 1.2.3.4 // initially prev = 1, current = 2 // Final expression will be current = 1^2^3^2^1, // as we know that bitwise XOR of two same // numbers will always be 0 i.e; 1^1 = 2^2 = 0 // After the evaluation of expression current = 3 that // means it has been moved by one node from its // previous position var next = current.next; current.next = prev; prev = current; current = next; } head_ref = prev; } // Function to push a node function push(new_data) { // Allocate node var new_node = new Node(); // Put in the data new_node.data = new_data; // Link the old list off the new node new_node.next = (head_ref); // Move the head to point to the new node (head_ref) = new_node; } // Function to print linked list function printList() { var temp = head_ref; while (temp != null) { document.write(temp.data + " "); temp = temp.next; } } // Driver code push(20); push(4); push(15); push(85); document.write("Given linked list<br/>"); printList(); reverse(); document.write("<br/>Reversed Linked list <br/>"); printList(); // This code is contributed by todaysgaurav. </script>

Output: Given linked list 85 15 4 20 Reversed Linked list 20 4 15 85

Time Complexity: O(n)
Reference :
http://discuss.joelonsoftware.com/default.asp?interview.11.564944.16
Alternate Solution :

C++

// C++ program to reverse a linked list using two pointers. #include <bits/stdc++.h> using namespace std; typedef uintptr_t ut; /* Link list node */ struct Node { int data; struct Node* next; }; /* Function to reverse the linked list using 2 pointers */ void reverse(struct Node** head_ref) { struct Node* current = *head_ref; struct Node* next; while (current->next != NULL) { next = current->next; current->next = next->next; next->next = (*head_ref); *head_ref = next; } } /* Function to push a node */ void push(struct Node** head_ref, int new_data) { struct Node* new_node = new Node; new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } /* Function to print linked list */ void printList(struct Node* head) { struct Node* temp = head; while (temp != NULL) { printf("%d ", temp->data); temp = temp->next; } } /* Driver program to test above function*/ int main() { /* Start with the empty list */ struct Node* head = NULL; push(&head, 20); push(&head, 4); push(&head, 15); push(&head, 85); printf("Given linked list\n"); printList(head); reverse(&head); printf("\nReversed Linked list \n"); printList(head); return 0; }

Python3

# Python3 program to reverse a linked list using two pointers. # A linked list node class Node : def __init__(self): self.data = 0 self.next = None # Function to reverse the linked list using 2 pointers def reverse(head_ref): current = head_ref next= None while (current.next != None) : next = current.next current.next = next.next next.next = (head_ref) head_ref = next return head_ref # Function to push a node def push( head_ref, new_data): new_node = Node() new_node.data = new_data new_node.next = (head_ref) (head_ref) = new_node return head_ref # Function to print linked list def printList( head): temp = head while (temp != None) : print( temp.data, end=" ") temp = temp.next # Driver code # Start with the empty list head = None head = push(head, 20) head = push(head, 4) head = push(head, 15) head = push(head, 85) print("Given linked list") printList(head) head = reverse(head) print("\nReversed Linked list ") printList(head) # This code is contributed by Arnab Kundu

Output: Given linked list 85 15 4 20 Reversed Linked list 20 4 15 85

Thanks to Abhay Yadav for suggesting this approach.
This article is contributed by Shashank Mishra ( Gullu ). If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to . See your article appearing on the GeeksforGeeks main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Article Tags :

Linked List

Bitwise-XOR

Reverse

Practice Tags :

Linked List

Reverse

Read Full Article

Reversing a Linked List: Easy as 1, 2, 3

Sergey Piterman

Follow

Aug 9, 2018 · 9 min read

A common interview question asked at larger companies, reversing a linked list is a problem I’ve seen trip up a lot of engineers throughout my time at Outco.

Often being unable to solve this problem stems from an engineer not being familiar with what linked lists are ahead of time, or not understanding the difference between a linked list and an array.

This post assumes that you know what a linked list is, and some of its basic properties. If you don’t, here’s a good primer on Geeks for Geeks:

Problem Statement

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

Example:

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

Example

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

Recursive Approach

The recursive approach to reverse a linked list is simple, just we have to divide the linked lists in 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.

Recursive Approach

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)

---