Reverse A Linked List

November 12, 2019

We begin with a simple list:

(define xs '(1 2 3 4 5 6 7))

Scheme provides a built-in function to reverse a list; it returns a newly-allocated list and does not modify the original list:

> (reverse xs)
(7 6 5 4 3 2 1)
> xs
(1 2 3 4 5 6 7)

We write a function rev that does the same thing as Scheme’s reverse:

(define (rev xs)
  (let loop ((xs xs) (zs (list)))
    (if (null? xs) zs
      (loop (cdr xs) (cons (car xs) zs)))))
> (rev xs)
(7 6 5 4 3 2 1)
> xs
(1 2 3 4 5 6 7)

Sometimes you want to reverse a list in-place:

(define (rev! xs)
  (let loop ((prev (list)) (curr xs))
    (if (null? curr) prev
      (let ((next (cdr curr)))
        (set-cdr! curr prev)
        (loop curr next)))))
> (set! xs (rev! xs))
> xs
(7 6 5 4  3 2 1)
> (set! xs (rev! xs))
> xs
(1 2 3 4 5 6 7)

You can run the program at https://ideone.com/Vz2Qi7.

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: