Partial List Reversal

February 9, 2018

Looking at some of the proposed solutions to the student’s problem reminded me why I don’t like C. Fortunately, this is a simple task in Scheme:

(define (list-part-rev xs start finish)
  (let*-values (((temp end) (split finish xs))
                ((beginning middle) (split start temp)))
    (append beginning (reverse middle) end)))
> (list-part-rev '(0 1 2 3 4 5 6 7 8 9) 3 6))
(0 1 2 5 4 3 6 7 8 9)

This is simple and clear, written about as fast as I can type. The first split picks off the end of the list, the second split picks off the beginning and middle of the list, and the append puts the pieces back together. I can’t imagine how an early second-semester C programmer, not entirely confident in his knowledge of the language, even begins to write a program like this. Even worse, neither the student who was asking for help, nor any of the people who came to his aid, split the task into sub-tasks, each in its own function; all of the solutions were single, monolithic functions, and I wasn’t convinced that any of them would work, although I confess that I didn’t look very hard at the solutions. I hope the professor properly teaches his students to modularize code into functions.

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

Advertisements

Pages: 1 2

6 Responses to “Partial List Reversal”

  1. Also simple in perl:

    sub partial_reverse {
      my ($s,$e,@l) = @_;
      splice @l, $s, 0, reverse splice @l, $s, $e-$s;
      return @l;
    }
    
    @q = partial_reverse( 3, 6, 0..9 );
    print "@q\n";
    
  2. matthew said

    If it’s a C problem, presumably the student is expected to reverse the sublist in place, rather than build up new lists, so it’s really an exercise in pointer manipulation rather than calling library functions. Here’s a partial solution that does the interesting bit, reversing the front n elements of a list. To reverse a sublists starting at the nth position, just step down the list n times (and take care to update the right pointer to the reversed section). Idea is to take elements of the front of the list s and transfer them to t, which naturally comes out in reverse. We record the last element of t and update it appropriately when we have done reversing. It doesn’t seem very amenable to separation into useful subfunctions:

    #include <assert.h>
    #include <stdio.h>
    #include <stdlib.h>
    
    struct List {
       List(int n0, List* next0) : n(n0),next(next0) {}
       ~List() { delete(next); }
       int n;
       List *next;
    };
    
    List *revn(int n, List *s) {
       assert(n > 0);
       List *t = nullptr;  // Reversed items go here
       List *t0 = nullptr; // Store last cell of t here
       for ( ; n > 0 && s; n--) {
          List *s0 = s; // Front of remainder
          s = s->next;  // Move s on one
          s0->next = t; // Transfer s0 to t
          t = s0;       // And update t itself
          if (!t0) t0 = t; // Record last item in t list
       }
       if (s && t0) {
          t0->next = s;
       }
       return t;
    }
    
    int main(int argc, char *argv[]) {
       int m = strtol(argv[1],0,0);
       int n = strtol(argv[2],0,0);
       List *s = 0;
       for ( ; m != 0; m--) s = new List(m,s);
       s = revn(n,s);
       for (List *t = s; t; t = t->next) {
          printf("%d ", t->n);
       }
       printf("\n");
       delete s;
    }
    
  3. Globules said

    Here’s a Haskell version.

    import Prelude hiding (head, tail)
    
    -- Reverse that part of the list whose zero-based indices are in the range
    -- [lo, hi).  No error checking is done on the arguments.
    reverseSublist :: Int -> Int -> [a] -> [a]
    reverseSublist lo hi xs = let (head, ys) = splitAt lo xs
                                  (middle, tail) = splitAt (hi - lo) ys
                              in head ++ reverse middle ++ tail
    
    main :: IO ()
    main = print $ reverseSublist 3 6 [0..9]
    
    $ ./revsub 
    [0,1,2,5,4,3,6,7,8,9]
    
  4. Milbrae said
    def revlist(l, b, e):
        length = len(l)
        if e > length: return l
        if b < 0: return l
        if b >= e: return l
        return list(l[0:b]) + list(reversed(l[b:e])) + list(l[e:length])
    
    if __name__ == "__main__":
        l = [0,1,2,3,4,5,6,7,8,9]
        print (revlist(l, 3, 6))
    
  5. Daniel said

    Here’s a solution in C.

    #include <stdbool.h>
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct node {
      struct node* next;
      int val;
    } node_t;
    
    void print_list(node_t* list) {
      printf("[");
      node_t* current = list;
      while (true) {
        if (current != list) printf(", ");
        printf("%d", current->val);
        if (current->next == NULL) break;
        current = current->next;
      }
      printf("]\n");
    }
    
    static void reverse_list_front(node_t** head_pp, size_t end) {
      if (*head_pp == NULL) return;
      node_t* prev_p = *head_pp;
      node_t* node_p = prev_p->next;
      for (size_t i = 1; i < end; ++i) {
        if (node_p == NULL) break;
        node_t* next_p = node_p->next;
        node_p->next = prev_p;
        prev_p = node_p;
        node_p = next_p;
      }
      (*head_pp)->next = node_p;
      *head_pp = prev_p;
    }
    
    void reverse_list_section(
        node_t** head_pp, size_t start, size_t end) {                  
      if (*head_pp == NULL) return;
      for (size_t i = 0; i < start; ++i) {
        if (*head_pp == NULL) return;
        head_pp = &((*head_pp)->next);
      }
      reverse_list_front(head_pp, end - start);
    }
    
    int main(void) {
      size_t n = 10;
      node_t nodes[n];
      for (size_t i = 0; i < n; ++i) {
        nodes[i].val = i;
        nodes[i].next = i+1 < n ? &(nodes[i+1]) : NULL;
      }
      node_t* list = &nodes[0];
      printf("list:\n  ");
      print_list(list);
      reverse_list_section(&list, 3, 6);
      printf("reverse_list_section(list, 3, 6):\n  ");
      print_list(list);
      return EXIT_SUCCESS;
    }
    
    

    Output:

    list:
      [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    reverse_list_section(list, 3, 6):
      [0, 1, 2, 5, 4, 3, 6, 7, 8, 9]
    
  6. Daniel said

    @Milbrae, Python’s lists are “really variable-length arrays”, not linked lists.
    https://docs.python.org/2/faq/design.html#how-are-lists-implemented

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: