Reverse A Linked List

November 12, 2019

We’ve done this before, but I saw questions asked about this task on three different beginner-programming forums this weekend (it must that that time in the semester when teachers introduce linked lists), and it never hurts to do some basic drill.

Your task is to write a program that reverses a linked list. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
2 Comments »

2 Responses to “Reverse A Linked List”

  1. Daniel said
    November 14, 2019 at 3:10 AM

    Here’s a solution in C.

    #include <stdio.h>
#include <stdlib.h>

typedef struct node {
  int val;
  struct node* next;
} node_t;

void reverse(node_t** list) {
  node_t* prev = NULL;
  node_t* node = NULL;
  node_t* next = *list;
  while (next != NULL) {
    prev = node;
    node = next;
    next = next->next;
    node->next = prev;
  }
  *list = node;
}

void print_list(node_t* list) {
  while (list != NULL) {
    printf("%d", list->val);
    if (list->next != NULL)
      printf("->");
    list = list->next;
  }
  printf("\n");
}

int main(int argc, char* argv[]) {
  node_t* list = NULL;
  for (int i = argc - 1; i > 0; --i) {
    node_t* node = malloc(sizeof(node_t));
    node->val = atoi(argv[i]);
    node->next = list;
    list = node;
  }
  printf("list:\n  ");
  print_list(list);
  printf("reversed(list):\n  ");
  reverse(&list);
  print_list(list);
  while (list != NULL) {
    node_t* next = list->next;
    free(list);
    list = next;
  }
  return EXIT_SUCCESS;
}

    Example:

    $ ./a.out 1 2 3 4 5
list:
  1->2->3->4->5
reversed(list):
  5->4->3->2->1
  2. matthew said
    November 14, 2019 at 7:52 PM

    Here’s a variation on Daniel’s solution, using some C++ features. The actual in-place list reverse is neatly expressed as an iterated rotation of list elements:

    #include <stdlib.h>
#include <iostream>

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

template <typename T>
void rotate3(T &a, T &b, T &c) {
  T tmp = a; a = b; b = c; c = tmp;
}

Node *reverse(Node *node) {
  Node *prev = nullptr;
  while (node) rotate3(prev,node,node->next);
  return prev;
}

std::ostream &operator<<(std::ostream &ostr, Node *node) {
  for( ; node; node = node->next) {
    ostr << node->val << (node->next ? "->" : "");
  }
  return ostr;
}

int main(int argc, char *argv[]) {
  Node *list = nullptr;
  for (int i = argc - 1; i > 0; --i) {
    Node *node = new Node;
    node->val = atoi(argv[i]);
    node->next = list;
    list = node;
  }
  std::cout << "list: " << list << "\n";
  list = reverse(list);
  std::cout << "reversed: " << list << "\n";
  while (list) {
    Node *next = list->next;
    delete list;
    list = next;
  }
}

    $ g++ -Wall reverse.cpp -o reverse
$ ./reverse 1 2 3 4 5
list: 1->2->3->4->5
reversed: 5->4->3->2->1

Leave a comment