Reversing a Linked List

If we had to reverse the elements of an array we would have to iterate over then entire array and swap the ith element with the (n-i-1)th element where n is the size of the array.

Now in a linked list we are not required to swap the data in the nodes. Instead we can achieve the same by just reversing the pointers, initializing the head to the last element of the given linked list and point the head of the original linked list to null.

So we will create 2 variables; one of them will always point to the node that the current node needs to point at, and the other will always point to the node the current node is currently pointing at. If we iterate till the current node – starting from head is not ‘null’ then we would have reversed the entire linked list.

static void reverse_linked_list(LinkedList l) {
        Node prev = null;
        Node temp = l.head;
        while (l.head != null) {
            temp = l.head.next;
            l.head.next = prev;
            prev = l.head;
            l.head = temp;
        }
        l.head = prev;
}