Write a function to Reverse a Linked List

Today we will see how to reverse a Linked List in O(n) time complexity.
Examples :
Input - 1->2->3->null 
Output - 3->2->1->null
Input - null 
Output - null 
Input - 1->null 
Output - 1->null

Iterative Method

Iterate trough the linked list. In loop, change next to prev, prev to current and current to next.
Below is the complete code in java for reverse a Linked List

class LinkedList {
 
    static Node head;
 
    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;
    }
 
    // prints content of double linked list
    void printList(Node node) {
        while (node != null) {
            System.out.print(node.data + " ");
            node = node.next;
        }
    }
 
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.head = new Node(100);
        list.head.next = new Node(20);
        list.head.next.next = new Node(5);
        list.head.next.next.next = new Node(30);
         
        System.out.println("Given Linked list");
        list.printList(head);
        head = list.reverse(head);
        System.out.println("");
        System.out.println("Reversed linked list ");
        list.printList(head);
    }
}

//output
//Given linked list
//100 20 5 30 
//Reversed Linked list 
//30 5 20 100 

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

 Hope you like it. Please comment for any doubts.
 Happy Learning !!!

SHARE

Onlinecodegeek