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

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