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

2 Responses to “Reverse A Linked List”

  1. Daniel said

    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

    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 Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: