How to reverse a singly linked list using only two pointers?

Question

I wonder if there exists some logic to reverse a singly-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;
    }
    first = q;
}

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?

Solution 1

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

Solution 2

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() {
    // curNode traverses the list, first is reset to empty list.
    struct node *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.
        struct node *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.

Solution 3

#include <stddef.h>

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

Node * reverse(Node *cur) {
    Node *prev = NULL;
    while (cur) {
        Node *temp = cur;
        cur = cur->next; // advance cur
        temp->next = prev;
        prev = temp; // advance prev
    }
    return prev;
}

Solution 4

Here's the code to reverse a singly linked list in C.

And here it is pasted below:

// reverse.c

#include <stdio.h>
#include <assert.h>

typedef struct node Node;
struct node {
    int data;
    Node *next;
};

void spec_reverse();
Node *reverse(Node *head);

int main()
{
    spec_reverse();
    return 0;
}

void print(Node *head) {
    while (head) {
        printf("[%d]->", head->data);
        head = head->next;
    }
    printf("NULL\n");
}

void spec_reverse() {
    // Create a linked list.
    // [0]->[1]->[2]->NULL
    Node node2 = {2, NULL};
    Node node1 = {1, &node2};
    Node node0 = {0, &node1};
    Node *head = &node0;

    print(head);
    head = reverse(head);
    print(head);

    assert(head == &node2);
    assert(head->next == &node1);
    assert(head->next->next == &node0);

    printf("Passed!");
}

// Step 1:
//
// prev head  next
//   |    |    |
//   v    v    v
// NULL  [0]->[1]->[2]->NULL
//
// Step 2:
//
//      prev head  next
//        |    |    |
//        v    v    v
// NULL<-[0]  [1]->[2]->NULL
//
Node *reverse(Node *head)
{
    Node *prev = NULL;
    Node *next;

    while (head) {
        next = head->next;
        head->next = prev;
        prev = head;
        head = next;
    }

    return prev;
}

Solution 5

Robert Sedgewick, "Algorithms in C", Addison-Wesley, 3rd Edition, 1997, [Section 3.4]

In case that is not a cyclic list ,hence NULL is the last link.

typedef struct node* link;

struct node{
    int item;
    link next;
};

/* you send the existing list to reverse() and returns the reversed one */

link reverse(link x){
    link t, y = x, r = NULL;
    while(y != NULL){
        t = y->next;
        y-> next = r;
        r = y;
        y = t;
    }
    return r;
}

View more solutions

Comments

[kajaco]

possible duplicate: stackoverflow.com/questions/818443/…

[paxdiablo]

Not really, that's two queues rather than two pointers.

[GManNickG]

Because you're here to help, and not play a rep game?

[Admin]

GMan: that's the thing, I'm not sure I'm helping anyone, even him, if he can't follow through.

[oneAday]

You're helping those of us who read and get something from the questions and answers. I found it insightful.

[Karussell]

reversing in O(1) could be done for double linked lists. see my answer.

[Dane]

Almost all answers here have used 3 pointers !!

[Left For Archive]

…and a new 64-bit compatibility issue is born, if you're not careful. You're unlikely to buy any performance this way either.

[poundifdef]

This will not affect the time complexity - that is, it won't make the solution any better than linear time. I mean, you might save 4 or 8 bytes of memory, but that won't change the overall complexity of the algorithm.

[Jonathan Leffler]

I'm not sure about 'obvious errors' in the original. Design-wise, not passing the head of the list in and not returning the new head is a bad idea. The only bug, though, is the last line in the reverse() function should be setting first, I believe. Otherwise, the original code worked OK when plugged into your neat test harness. You get +1 from me even so - but an explanation of what you consider the 'obvious errors' would improve your answer.

[paxdiablo]

@rascher, time complexity was the second part of the question. The first part had to do with reducing the number of pointers required.

[Admin]

Yes, q = first was biggest error I had in mind, though I consider the confusion over where the input is coming from and how reverse returns a value to be two more; I suppose it was my fault for not looking at it any further than that.

[Will]

I think the original poster was looking for a cheap C trick. In my experience - and I have profiled it :) - the typical avoiding intermediary tricks are actually slower than just using an intermediary.

[Steve Jessop]

I think "should" is overstating the case a bit. Your C compiler "might" do a tail-call optimization, and it's easy enough to check for a given compiler/options whether it does or not: look at the disassembly. Or give it a few million nodes and see if it crashes ;-)

[aks]

Isn't there a bug in the above code? Inside the while loop, you are creating a new 'next' pointer each time. So if there are N nodes in the linked list, you are creating N new pointers and you are not freeing or deleting them. I think it would be correct if you create the 'next' pointer before the while loop and just make the assignment 'next = root->next' inside the while loop.

[Admin]

@aks: There is no leak. Notice malloc/etc. are not called so there isn't any need to free. The variable 'next' is scoped to the loop, but that's perfectly okay.

[Kevin Kibler]

Very elegant. Reusing the first pointer on the linked list itself allows the solution to use only 2 extra pointers, but 3 total pointers are still necessary for this.

[Blastfurnace]

(1) This doesn't reverse the linked list. (2) You have an infinite loop any time node->next != null

[Mr. Amit Kumar]

Contact me for any problem's C implementation.

[Green goblin]

@MohdAdnan, did you care understanding the code? The code is to reverse the linked list only. FYI, where did you get the logic for printing the linked list? I don't see any print statement here right?

[Mohammad Adnan]

Yes Sorry for that. I was suppose to comment on question below and by mistakenly commented here. But Now I just go through the code you wrote and I found one possible flaw . You are not collecting value that is returned by recursive call so I believe that should be changed to temp = reverse(root->next);

[Mohammad Adnan]

question is to reverse a linked list not print linked list in reverse order.

[achedeuzot]

Thanks for the awesome ASCII art for explaining :)

[Mike G]

How is this correct. You are using more than two pointers, its just hidden on the stack every time you do a function call.

[njzk2]

you are using first as a variable (hidden by the fact that you actually use first->link, but still it is a variable.)

[Quentin]

As clever and undecipherable as that may be, you're in trouble if sizeof(size_t) < sizeof(ListNode*)... you should use std::uintptr_t.

[ideasman42]

This assumes an int is the same size as a pointer, it wont work on amd64 systems (you could use intptr_t). While interesting - swapping this way is sub-optimal on modern systems.

[Yash]

You are using first, curNode and nxtNode, total of three pointers for this. how come this is a two pointer solution?

[paxdiablo]

@Yash, read again, two extra pointers on top of first. The same way the OP's three-pointer solution had first, p, q and r.

[Yash]

@paxdiablo oh! my bad. Sorry, I misunderstood the question. Thanks :)

[Degustaf]

The question is looking for a C solution, not one in Java

[ernesto]

The question is more about doing the reverse operation with only two additional pointers (or references). Whether its C or Java the logic is same.

[Jagdish]

Even if there is no leak, What is the need of declaring next every time, as aks mentioned, "it would be correct if you create the 'next' pointer before the while loop and just make the assignment 'next = root->next' inside the while loop.", Isn't it?

[Admin]

I like your linked list literals, that is neat.

[Green goblin]

@MohdAdnan: We don't need to collect the return value of reverse. Please note that temp will be the new root of linked list and we need its return value only in caller function.

[MakeTheTrumpetsBlow]

Hello! I know this question is old, but would you mind explaining what happens in this function, and why it works. :) Thanks!

[Dane]

The link is broken, but I'm sure swapping 2 numbers using XOR is old-school :)

[Raju Muke]

node is not a pointer , We have just passing head as node. Let me know if you need more clarification

[satvik.t]

The OP's intent was to use 2 variables, regardless of whether they are pointers or variables.

[user1095108]

you can do it in constant time, bruh.

[user1095108]

blah, XOR list can be reversed in constant time.

[Jonathan Leffler]

Note Is it a good idea to typedef pointers? — short answer: No.

[Jonathan Leffler]

@Jagdish — there is no cost to declaring the variable in the loop and limiting the scope of variables is a good idea. Look at the optimized assembler output for a version with the variable defined in the loop and one with the variable defined outside the loop.

[Jonathan Leffler]

The one-line versions run into sequencing problems due to a lack of sequence points. The results are unreliable at best. These methods for swapping are not great. They are party tricks rather than real code.