TheHappieCat: Reversing Linked Lists

reverse_linked_list.cpp

// Example program
#include <iostream>
#include <string>

struct Node {
    int data;
    Node* next;
};

Node* create_node(int node_data){
    
    //Create the node.
    Node* n = new Node();
    
    //Set the data.
    n->data = node_data;   
    
    return n;
}

//Create a new node and set the inputted node's next pointer
//to the new node. Returns a reference to the new node.
Node* push_node(Node* curr, int node_data){
    
    if(curr == NULL){
        return NULL;   
    }
    
    Node* n = create_node(node_data);
    
    //Set the next pointer of the current node to the new node.
    curr->next = n;
    
    return n;
}

//Creates a linked list with the number of nodes equal to the inputted size.
//Node data is set to 0, 1, 2, ... through "N" sequentially.
//Returns a reference to the head of the list.
Node* create_linked_list(int size){
    
    if(size < 1){
        return NULL;   
    }
    
    Node* head = create_node(0);
    Node* curr = head;
    
    for(int i = 1; i < size; i++){
        curr = push_node(curr, i);
    }
    
    return head;
}

void print_linked_list(Node* head){

    Node* curr = head;

    while(curr != NULL){
       std::cout << curr->data;
       curr = curr->next;
    }
    
    std::cout << std::endl;
}

void reverse_list(Node* head){
    
 //Your code here.
 
 
 
 
 
 
 
    
}

int main()
{
    Node* head = create_linked_list(10);
    print_linked_list(head);
    
    //You should see: 0123456789
    
    reverse_list(head);
    print_linked_list(head);
    
    //You should see: 9876543210
    
    return 0;
}

Node* reverse_node(Node* current, Node* newNext) {
    if(current->next != nullptr) {
        return reverse_node(current->next, current);
    }
    current->next = newNext;
    return current;
}


void reverse_list(Node** head){
    if(*head == nullptr) { return; }
    *head = reverse_node(*head, nullptr);
}

Tail recursive, so still efficient (O2)

@jvanbruegge Do you mean this?

Node* reverse_node(Node* current, Node* newNext) {
    Node* newHead;
    if(current->next != nullptr) {
        newHead = reverse_node(current->next, current);
    } else {
        newHead = current;
    }
    current->next = newNext;
    return newHead;
}

void reverse_list(Node* head)
{
    if (head != nullptr)
    {
        std::vector<Node*> nodes;
        auto current = head;
        while(current != nullptr)
        {
            nodes.push_back(current);
            current = current->next;
        }
        
        {
            auto front = nodes.begin();
            auto back = std::prev(nodes.end());
            for (; front < back; ++front, --back)
            {
                std::swap((*front)->data, (*back)->data);
            }
        }
    }
}

Iterative solution using STL, using O(n) space and O(n) time.
Assumption:

• Data type cheaply swappable/movable
• List can get long, prefer heap allocation to stack overflow.

Further improvement:

• Can do a full list traverse first and reserve the vector's capacity to avoid reallocation. This will save allocation time if list is long.

I made a solution avoiding the pointer to pointer "Node **" signature.

void reverse_list(Node* head) {
	if (head != NULL && head->next != NULL) {
		Node* curr = head;
		Node* next = head->next;
		Node* nextNext = NULL;
		while (next != NULL) {
			nextNext = next->next;
			next->next = curr;
			curr = next;
			next = nextNext;
		}
		head->next->next = curr;
		head->next = curr->next;
		curr->next = NULL;
		int headData = head->data;
		head->data = curr->data;
		curr->data = headData;
	}
}

Commented version

This solution has a time complexity of O(n + m) where n is the size of the list and m the size of the data. In space it takes only O(1) since we only store a fixed amount of data in the whole execution.
Note that the solution requires a swap of the data between the head and tail, this could be very slow if we were dealing with a list of images in memory, for example.

With the Node ** signature you will kinda break all other references to the list, because they now point to the last Node- which has no further Nodes attached. With a separate HEAD not containing any data but the pointer to the first real Node you'd fix this.
Btw., why not use C++-Style nullptr instead of C-Style NULL?

Here is my (probably) slow solution to the problem, using the same function prototype as written above.

void reverse_list(Node* head) {
	// Set up variables
	int size = 0;
	Node* curr = head;

	// Get linked list size
	while (curr != NULL) {
		size++;
		curr = curr->next;
	}

	// Create array to copy to
	int copy[size];

	// Copy to array in reverse
	curr = head;
	for (int i = size - 1; i > -1; i--) {
		copy[i] = curr->data;
		curr = curr->next;
	}

	// Copy array back into linked list
	curr = head;
	for (int i = 0; i < size; i++) {
		curr->data = copy[i];
		curr = curr->next;
	}
}

Avoiding Node** almost like your implementation but checking 1 step further

void reverse_list(Node* head){
    
 //Your code here.
 if(head->next == NULL) return;
 Node* current = new Node();
 current->next = head->next;
 current->data = head->data;

 Node* previous = NULL;
 Node* next = NULL;

 while(current->next !=NULL){
 	next  = current->next;
 	current->next = previous;
 	previous = current;
 	current = next;
 }

 head->next = previous;
 head->data = current->data; 
 delete current;
}

Here is my solution, I think is not the best but at least it works...

void reverse_list(Node* head){
	if(head != NULL){
 		int i, *val, n;
 		Node* curr = head;
 		for(i=0; curr != NULL ;i++)
        	curr = curr->next;
 		curr = head;
 		n=i;
  		val = (int*)malloc(n*sizeof(int));
 		for(i=n-1; i>=0; i--){
                     val[i]=curr->data;
                     curr= curr->next;
 		}	
 		curr = head;
 		for(i=0; i<n; i++){
                     curr->data = val[i];
                     curr = curr -> next;
 		} 
 	free(val);
	}
}

In a way, this would technically work, but you'd have to keep the tail beforehand to make the new head. Or modify the call to return the new head.

// Linked list is flipped, but we lose the head so we'll create a sub-function for it and move some stuff around in memory to work things out
// This will modify memory locations of the nodes/their data
void reverse_list(Node* head){
    static Node*(*rev_)(Node*) = [](Node* head)->Node*{
        if(!head || !head->next) return head;
        Node* new_head = rev_(head->next);
        head->next->next = head;
        head->next = nullptr;
        return new_head;
    };
    // At the end the head and new head need to be swapped. We must also not disconnect the old head
    Node* new_head = rev_(head->next);
    if(!new_head) return;
    // Now rewire the two ends
    head->next->next = new_head; // head and new_head will swap soon, so point this node to where head's going to be
    head->next = nullptr;
    Node temp = *head;
    *head = *new_head;
    *new_head = temp;
    return;
}

//Or, if we can modify the call directly:
Node* reverse_list(Node* head){
    if(!head || !head.next) return head;
    Node* new_head = reverse_list(head.next);
    head.next->next = head;
    head.next = nullptr;
    return new_head;
}

@lucaslugao I also kept the original method signature, but I think mine is a bit simpler:

void reverse_list(Node* head){
    if (head != NULL && head->next != NULL) {
        Node *prev = NULL, *cur = head, *next, *store = head->next;
        while (cur != NULL) {
            next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }
        Node storeNode = *head;
        *head = *prev;
        *prev = storeNode;
        store->next = prev;
    }
}

Commented Solution

However, I think @Snaipe's solution is best.

It took me 2 hours to do:

#include <utility> // std::swap
void reverse_list(Node*& head){
    using std::swap;

    if  ( !head ) return;
    Node*& node = head;
    Node*  next = head->next;
    node-> next = nullptr; // tail
    while( next )
        swap( next->next, node ),
        swap( next, node );
}

First version:

#include <utility> // std::swap
void reverse_list(Node* head){    /* reverse_list(Node* & head) // ?!          */
                                  /* Reference would make everything easier... */
    // My code here:
    // This code is not guaranteed to be thread-safe.
    Node* old_head = head;       /* This can be deleted if 'head' argument is passed by reference */
    Node* old_next = head->next; /* This can be deleted if 'head' argument is passed by reference */

    using std::swap;

    // some border cases:
    if ( !head ) return;
    if ( !head->next ) return;
    if ( !head->next->next ) {
        swap( head->next, head->next->next );
        return;
    }

    // work really starts here:
    Node*& node = head;
    Node*  next = head->next;
    node-> next = nullptr; // tail
    do {
        swap( next->next, node );
        swap( next, node );
    } while ( next );
    // 'head' is new head now

    /* 'head' in 'main' function is still pointing to 'old_head',
       because 'head' is passed by value, not by reference.
       so... moving new head to place where old head was, is required.  */
    swap( *old_head, *head );

    /* also 'next' pointer in one node before tail, needs 're-pointing' */
    old_next->next = head; // 'head' is really pointing to tail of new linked list
}

void reverse_list(Node*& head) {
	int numberOfNodes = 0;
	Node* curr = head;
	while (curr != NULL) {
		numberOfNodes++;
		curr = curr->next;
	}
	curr = head;
	for (int i = numberOfNodes - 1; i > 0; i--) {
		Node* insertLocation = curr;
		for (int j = 0; j < i; j++) {
			insertLocation = insertLocation->next;
		}
		Node* temp = curr->next;
		curr->next = insertLocation->next;
		insertLocation->next = curr;
		curr = temp;
	}
	head = curr;
}

Looking at other solutions this seems horrible.

things...

void reverse_list(Node*& head) {
  if (!head) return;

  auto cur  = head;
  Node*prev = nullptr;

  while (cur->next) {
    std::swap(prev, cur->next);
    std::swap(cur, prev);
  }
  std::swap(cur->next, prev);
  head = cur;
}

@cdacamar Your solution is similar to mine.
Even "value-flow" is EXACTLY the same...
void reverse_list(Node*& head) { /* */ }

Mine:

    if  ( !head ) return;
    Node*& node = head;
    Node*  next = head->next;
    node-> next = nullptr; // tail
    while( next )
        swap( next->next, node ),
        swap( next, node );

and yours:

  if (!head) return;

  auto cur  = head;
  Node*prev = nullptr;

  while (cur->next) {
    std::swap(prev, cur->next);
    std::swap(cur, prev);
  }
  std::swap(cur->next, prev);
  head = cur;

void reverse_list(Node** head){

//Your code here.
Node* prev=NULL;
Node* curr=head;
Node nex=NULL;
while(curr != NULL){
// std::cout << curr->data;
nex = curr->next;
curr->next=prev;
prev= curr;
curr = nex;

}
//head->next=NULL; 
*head=prev;

// the pointer issue was the last boss fight if you know what I mean

} // abadi

@MajsterTynek I was just making a solution I would have written for an interview. I suppose I could have opted for a more esoteric solution...

namespace std {

void swap(std::reference_wrapper<int> lhs, std::reference_wrapper<int> rhs) {
  swap(lhs.get(), rhs.get());
}

}

void reverse_list(Node*& head){
  std::vector<std::reference_wrapper<int>> v;
  auto node = head;
  while (node) {
    v.push_back(std::ref(node->data));
    node = node->next;
  }
  std::reverse(std::begin(v), std::end(v));
}