## Partial List Reversal

### February 9, 2018

We’re a few weeks into the beginning of a new school term, and the beginning-programmer message boards are swelling with questions from new students. This question caught my eye; I imagine it’s from a second-semester programming student who learned C in the first semester and is now taking a class in data structures:

Write a program that, given a linked list and two integer indices, reverses the portion of the list between the two indices. For instance, reversing the list [0,1,2,3,4,5,6,7,8,9] between indices 3 (inclusive) and 6 (exclusive) yields the list [0,1,2,5,4,3,6,7,8,9].

Your task is to help the student by writing a program to reverse a portion of a 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

### 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,0,0);
int n = strtol(argv,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

```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) {
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;
}
}

void reverse_list_section(
node_t** head_pp, size_t start, size_t end) {
for (size_t i = 0; i < start; ++i) {
}
}

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;
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