Reverse a linked list
You are given a Singly Linked List of integers. You need to reverse the Linked List by changing the links between nodes.

Input Format :

The first line of input contains a single integer T, representing the number of test cases or queries to be run. The first line of each test case contains the elements of the singly linked list separated by a single space and terminated by -1. Hence, -1 would never be a list element.

Output Format :

For each test case, print the reversed linked list. The elements of the reversed list should be single-space separated, terminated by -1. Print the output of each test case in a separate line.

Note :

You do not need to print anything, just return the head of the reversed linked list.

Constraints :

1

Question

Reverse a linked list

You are given a Singly Linked List of integers. You need to reverse the Linked List by changing the links between nodes.

Input Format :

The first line of input contains a single integer T, representing the number of test cases or queries to be run. 

The first line of each test case contains the elements of the singly linked list separated by a single space and terminated by -1. Hence, -1 would never be a list element.

Output Format :

For each test case, print the reversed linked list. The elements of the reversed list should be single-space separated, terminated by -1.

Print the output of each test case in a separate line.

Note :

You do not need to print anything, just return the head of the reversed linked list.

Constraints :

1 <= T <= 10
1 <= N <= 10^4
0 <= data <= 10^9

Where 'N' is the number of nodes in the linked list.

Time Limit: 1 sec

Accepted Answer

This can be solved both: recursively and iteratively.
The recursive approach is more intuitive. First reverse all the nodes after head. Then we need to set head to be the final node in the reversed list. We simply set its next node in the original list (head -> next) to point to it and sets its next to NULL. The recursive approach has a O(N) time complexity and auxiliary space complexity.
For solving the question is constant auxiliary space, iterative approach can be used. We maintain 3 pointers, current, next and previous, abbreviated as cur, n and prev respectively. All the events occur in a chain.
1. Assign prev=NULL, cur=head .
2. Next, repeat the below steps until no node is left to reverse:
2.1. Initialize n to be the node after cur. i.e. (n=cur->next)
2.2 Then make cur->next point to prev (next node pointer).
2.3. Then make prev now point to the cur node.
2.4. At last move cur also one node ahead to n.
The prev pointer will be the last non null node and hence the answer.

Accepted Answer

Recursive Approach

One way is to use recursion to reverse the list. Divide the linked list in two halves, the first node and the rest of the list. Reverse the second half using recursion and append the first half, that is the first node at the end of the reversed linked list. Return the head of the reversed linked list.

Algorithm

If the list contains only one node, return the head of the list.
Else, divide the list into two parts, first node and the rest of the linked list.
Call the reverse for the rest of the linked list.
Append the first node at the end of the reversed linked list, the linked list obtained in step 2.
Return the head of the reversed linked list, obtained in step 4.

Space Complexity: O(n)Explanation:

O(N), Where ‘N’ is the number of nodes in the linked list.

There can be at most ‘N’ recursive states which will take O(N) space. Thus, the final space complexity is O(N).

Time Complexity: O(n)Explanation:

O(N), Where ‘N’ is the number of nodes in the linked list.

There can be at most ‘N’ recursive states while reversing the linked. We are traversing the list only once, thus the final time complexity is O(N).

Java (SE 1.8)

/*

    Time Complexity: O(N)

    Space complexity: O(N)

    

    Where 'N' is the number of nodes in the list.



*/



public class Solution

{

public static Node reverseLinkedList(Node head)

    {

        // If list is empty or has just one node return it

        if (head == null || head.next == null)

        {

            return head;

        }



        // Reverse the rest of the list and put the first element at the end

        Node rest = reverseLinkedList(head.next);

        head.next.next = head;



        head.next = null;



        // Fix the head pointer

        return rest;

    }

}

C++ (g++ 5.4)

/*

    Time Complexity: O(N)

    Space complexity: O(N)

    

    Where 'N' is the number of nodes in the list.



*/



Node* reverseLinkedList(Node *head)

{

	// If list is empty or has just one node return it

	if(head == NULL || head->next == NULL){

		return head;

	}

	

    // Reverse the rest of the list and put the first element at the end 

    Node* rest = reverseLinkedList(head->next);

    head->next->next = head;

 

    head->next = NULL;

 

    // Fix the head pointer 

    return rest;

}

Python (3.5)

'''

    Time Complexity: O(N)

    Space complexity: O(N)



    Where N are the number of nodes in the list.



'''





def reverseLinkedList(head):



    # If list is empty or has just one node return it

    if(head == None or head.next == None):

        return head



    # Reverse the rest of the list and put the first element at the end

    rest = reverseLinkedList(head.next)

    head.next.next = head



    head.next = None



    # Fix the head pointer

    return rest

Accepted Answer

Iterative approach

Reverse the link of each node, starting from the head and moving towards the tail of the linked list. Take three-pointers, ‘curr’, ‘ahead’, ‘prev’. Initialize curr with the head node, ahead, and prev with NULL. Keep on iterating the linked list until ‘curr’ reaches NULL. Store the next node of the current node in ‘ahead’ before changing the next of the current node and point the next of the current node to ‘prev’ (pointer to the node just before the current node). This is the actual reversing of the links in the linked list. Point ‘prev’ node to ‘curr’ node and ‘curr’ node to ‘ahead’ node. At the end return the head of the reversed linked list.

Algorithm

Initialize three pointers prev as NULL, curr as head and ahead as NULL.
Iterate through the linked list and do following
a. Point ‘ahead’ to the next of the current node, ahead = curr->next
b. Point next of the curr node to ‘prev’, curr->next = prev.
c. Point the prev node to the curr node and curr node to the ‘ahead’ node.
Return ‘prev’ , as it will be the head of the reversed linked list and ‘curr’ will be pointing to NULL at this point.

Space Complexity: O(1)Explanation:

O(1)

Constant extra space is required.

Time Complexity: O(n)Explanation:

O(N), Where N is the number of nodes in the linked list.

Each node of the linked list is visited only once, thus the final time complexity is O(N).