-
-
Save anneomcl/13250a56c70d6f5b7c9cadecfd622e85 to your computer and use it in GitHub Desktop.
// 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; | |
} |
@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;
}
}
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;
}
}
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));
}
Tail recursive, so still efficient (O2)