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

Read

Discuss(20+)

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

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 of 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 of 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 of 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 of 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 of 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)
Auxiliary Space: O(1) since using space for prev and next

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; 
} 

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 next; 
        Node curr = head_ref; 
        while (curr.next != null) { 
            next = curr.next; 
            curr.next = next.next; 
            next.next = head_ref; 
            head_ref = next; 
        } 
    } 
  
    // 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 of 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 Abhijeet Kumar(abhijeet19403)

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 

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 current = head_ref; 
        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 
    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 of 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 Abhijeet Kumar(abhijeet19403)

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 current = head_ref; 
        var next; 
        while (current.next != null) 
        { 
            next = current.next; 
            current.next = next.next; 
            next.next = head_ref; 
            head_ref = next; 
        } 
    } 
  
    // 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 of 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 Abhijeet Kumar(abhijeet19403)  
</script>

Output:

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

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

Thanks to Abhay Yadav for suggesting this approach.
If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!

Last Updated : 11 Sep, 2023

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

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

Please Login to comment...