Reverse a singly linked list

Question

I would be wondered if there exists some logic to reverse the linked list using only two pointers.

The following is used to reverse the single linked list using three pointers namely p, q, r:

struct node
{
    int data;
    struct node *link;
};

void reverse()
{
    struct node *p = first,
                *q = NULL,
                *r;
    while (p != NULL)
    {
        r = q;
        q = p;
        p = p->link;
        q->link = r;
    }
    q = first;
}

Is there any other alternate to reverse the linked list? what would be the best logic to reverse a singly linked list, in terms of time complexity?

Answer 1

Yes. I'm sure you can do this the same way you can swap two numbers without using a third. Simply cast the pointers to a int/long and perform the XOR operation a couple of times. This is one of those C tricks that makes for a fun question, but doesn't have any practical value.

Can you reduce the O(n) complexity? No, not really. Just use a doubly linked list if you think you are going to need the reverse order.

Answer 2

Work out the time complexity of the algorithm you are using now and it should be obvious that it can not be improved.

Answer 3

Any alternative? No, this is as simple as it gets, and there's no fundamentally-different way of doing it. This algorithm is already O(n) time, and you can't get any faster than that, as you must modify every node.

It looks like your code is on the right track, but it's not quite working in the form above. Here's a working version:

#include <stdio.h>

typedef struct Node {
  char data;
  struct Node* next;
} Node;

void print_list(Node* root) {
  while (root) {
    printf("%c ", root->data);
    root = root->next;
  }
  printf("\n");
}

Node* reverse(Node* root) {
  Node* new_root = 0;
  while (root) {
    Node* next = root->next;
    root->next = new_root;
    new_root = root;
    root = next;
  }
  return new_root;
}

int main() {
  Node d = { 'd', 0 };
  Node c = { 'c', &d };
  Node b = { 'b', &c };
  Node a = { 'a', &b };

  Node* root = &a;
  print_list(root);
  root = reverse(root);
  print_list(root);

  return 0;
}

Answer 4

I hate to be the bearer of bad news but I don't think your three-pointer solution actually works. When I used it in the following test harness, the list was reduced to one node, as per the following output:

==========
4
3
2
1
0
==========
4
==========

You won't get better time complexity than your solution since it's O(n) and you have to visit every node to change the pointers, but you can do a solution with only two extra pointers quite easily, as shown in the following code:

#include <stdio.h>

// The list element type and head.

struct node { 
    int data;
    struct node *link;
};
static struct node *first = NULL;

// A reverse function which uses only two extra pointers.

void reverse() {
    struct node *nxtNode, *curNode;

    // curNode traverses the list, first is reset to empty list.

    curNode = first;
    first = NULL;

    // Until no more in list, insert current before first and advance.

    while (curNode != NULL) {
        // Need to save next node since we're changing the current.

        nxtNode = curNode->link;

        // Insert at start of new list.

        curNode->link = first;
        first = curNode;

        // Advance to next.

        curNode = nxtNode;
    }
}

// Code to dump the current list.

static void dumpNodes() {
    struct node *curNode = first;
    printf ("==========\n");
    while (curNode != NULL) {
        printf ("%d\n", curNode->data);
        curNode = curNode->link;
    }
}

// Test harness main program.

int main (void) {
    int i;
    struct node *newnode;

    // Create list (using actually the same insert-before-first
    // that is used in reverse function.

    for (i = 0; i < 5; i++) {
        newnode = malloc (sizeof (struct node));
        newnode->data = i;
        newnode->link = first;
        first = newnode;
    }

    // Dump list, reverse it, then dump again.

    dumpNodes();
    reverse();
    dumpNodes();
    printf ("==========\n");

    return 0;
}

This code outputs:

==========
4
3
2
1
0
==========
0
1
2
3
4
==========

which I think is what you were after. It can actually do this since, once you've loaded up first into the pointer traversing the list, you can re-use first at will.

Answer 5

No, nothing faster than the current O(n) can be done. You need to alter every node, so time will be proportional to the number of elements anyway and that's O(n) you already have.

Answer 6

Just for fun (although tail recursion optimization should stop it eating all the stack):

Node* reverse (Node *root, Node *end) {

    Node *next = root->next;
    root->next = end;

    return (next : reverse(next, root) : root);
}

root = reverse(root, NULL);

Answer 7

Solution using 1 variable (Only p):

typedef unsigned long AddressType;

#define A (*( AddressType* )&p )
#define B (*( AddressType* )&first->link->link )
#define C (*( AddressType* )&first->link )

/* Reversing linked list */
p = first;

while( first->link )
{
    A = A + B + C;
    B = A - B - C;
    A = A - B;
    C = A - C;
    A = A - C;
}

first = p;