I'm going to start with something really basic, which is the problem of reversing a simple linked list. I'll only add here the most important functions, building the rest of the solution is just not worth the reading space. For this post, and the rest, I will assume a simple linked list has the following structure:

1: struct node {

2: int data; //let's keep it simple, assume it's a list of integers

3: node* next; //pointer to the next node in the list

` 4: };`

There are two ways to do it, and both are pretty simple: iteratively and recursive. The interative solution looks something like this:

` 1: node* reverse_interative(node* head)`

` 2: {`

3: if (head == 0 || head->next == 0)

4: return head; //just return if the list is empty or has only one item

` 5: node* prev = 0;`

` 6: node* next = 0;`

7: while (head->next != 0) { //we go forward through the list

8: next = head->next; // remember the next item at each step

9: head->next = prev; // modify the pointer to the next item, to point at the previous item

10: prev = head; // at the next step we move forward, so prev is also moved forward

11: head = next; // go to the next element

` 12: }`

13: head->next = prev; // we stopped because (head->next == 0), so it's the last element which must become the head

14: return head;

` 15: }`

Recursively, it's even simpler:

1: node* reverse_recursive(node* head, node* prev) // start with prev = 0, for the first call

` 2: {`

3: if (head == 0) // if we're at the end, return the previous item, which is the end of the original list

4: return prev;

5: node* next = head->next; //keep the next item in a temp node

6: head->next = prev; // modify the pointer to the next item, to point at the previous item

7: return reverse_recursive(next, head); // do the same for the next item

` 8: }`

## No comments:

## Post a Comment