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

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