# [ACCEPTED]-How to reverse a singly linked list using only two pointers?-singly-linked-list

Score: 135

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

It 3 looks like your code is on the right track, but 2 it's not quite working in the form above. Here's 1 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;
}
``````
Score: 44

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

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

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

``````#include <stdio.h>

// The list element type and head.

struct node {
int data;
};
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, *nxtNode;
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.

// Insert at start of new list.
first = curNode;

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

// 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;
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 4 what you were after. It can actually do 3 this since, once you've loaded up `first` into 2 the pointer traversing the list, you can 1 re-use `first` at will.

Score: 25
``````#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;
}
``````

0

Score: 13

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

And here it is pasted 1 below:

``````// reverse.c

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

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

void spec_reverse();

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

}
printf("NULL\n");
}

void spec_reverse() {
// ->->->NULL
Node node2 = {2, NULL};
Node node1 = {1, &node2};
Node node0 = {0, &node1};

printf("Passed!");
}

// Step 1:
//
//   |    |    |
//   v    v    v
// NULL  ->->->NULL
//
// Step 2:
//
//        |    |    |
//        v    v    v
// NULL<-  ->->NULL
//
{
Node *prev = NULL;
Node *next;

}

return prev;
}
``````
Score: 4

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

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

``````typedef struct node* link;

struct node{
int item;
};

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

link t, y = x, r = NULL;
while(y 3 != NULL){
t = y->next;
y-> next 2 = r;
r = y;
y = t;
}
return 1 r;
}
``````
Score: 3

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

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

Score: 3

You need a track pointer which will track the list.

You 2 need two pointers :

first pointer to pick first node. second pointer to 1 pick second node.

Processing :

Move Track Pointer

Point second node to first node

Move First pointer one step, by assigning second pointer to one

Move Second pointer one step, By assigning Track pointer to second

``````Node* reverselist( )
{
Node *first = NULL;  // To keep first node
Node *second = head; // To keep second node
Node *track =  head; // Track the list

while(track!=NULL)
{
track = track->next; // track point to next node;
second->next = first; // second node point to first
first = second; // move first node to next
second = track; // move second node to next
}

track = first;

return track;
``````

}

Score: 3

Just for fun (although tail recursion optimization 1 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);
``````
Score: 2

``````
Node *pop (Node **root)
{
Node *popped = *root;

if (*root) {
*root = (*root)->next;
}

return (popped);
}

void push (Node **root, Node *new_node)
{
new_node->next = *root;
*root = new_node;
}

Node *reverse (Node *root)
{
Node *new_root = NULL;
Node *next;

while ((next = pop(&root))) {
push (&new_root, next);
}

return (new_root);
}
``````

0

Score: 2

To swap two variables without the use of 4 a temporary variable,

``````a = a xor b
b = a xor b
a = a xor b
``````

fastest way is to write 3 it in one line

``````a = a ^ b ^ (b=a)
``````

Similarly,

using two swaps

``````swap(a,b)
swap(b,c)
``````

solution 2 using xor

``````a = a^b^c
b = a^b^c
c = a^b^c
a = a^b^c
``````

solution in one line

``````c = a ^ b ^ c ^ (a=b) ^ (b=c)
b = a ^ b ^ c ^ (c=a) ^ (a=b)
a = a ^ b ^ c ^ (b=c) ^ (c=a)
``````

The same logic 1 is used to reverse a linked list.

``````typedef struct List
{
int info;
struct List *next;
}List;

{
q=p->next;
p->next=NULL;
while(q)
{
q = (List*) ((int)p ^ (int)q ^ (int)q->next ^ (int)(q->next=p) ^ (int)(p=q));
}
}
``````
Score: 2

Here's a simpler version in Java. It does 1 use only two pointers `curr` & `prev`

``````public void reverse(Node head) {
Node curr = head, prev = null;

curr.next = prev; //break the link to the next node and assign it to previous
prev = curr;      // we are done with previous, move it to next node
}

head.next = prev;     //for last node
}
``````
Score: 2
``````curr = head;
prev = NULL;

while (curr != NULL) {
next = curr->next; // store current's next, since it will be overwritten
curr->next = prev;
prev = curr;
curr = next;
}

``````

0

Score: 1

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

Score: 1
``````#include <stdio.h>
#include <malloc.h>

tydef struct node
{
int info;
} *start;

void main()
{
rev();
}

void rev()
{
struct node *p = start, *q = NULL, *r;
while (p != NULL)
{
r = q;
q = p;
}

start = q;
}
``````

0

Score: 1

I don't understand why there is need to 3 return head as we are passing it as argument. We 2 are passing head of the link list then we 1 can update also. Below is simple solution.

``````#include<stdio.h>
#include<conio.h>

struct NODE
{
struct NODE *next;
int value;
};

typedef struct NODE node;

void alloc(node **p);

void main()
{
clrscr();
getch();
}
void alloc(node **p)
{
node *temp;
temp = (node *) malloc( sizeof(node *) );
temp->next = NULL;
*p = temp;
}
{
node *temp,*new_node;
alloc(&new_node);
new_node->value = val;
{
return;
}
temp->next = new_node;
}
{
node *temp;
int index=0;
printf ("\n\n");
{
printf (" List is Empty \n");
return;
}
for (temp=head; temp != NULL; temp=temp->next,index++)
printf (" %d ==> %d \n",index,temp->value);
}
{
{
}
}
``````
Score: 0

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

Score: 0

You can have solution of this problem with 3 help of only one extra pointer, that has 2 to be static for the reverse function. It's 1 in O(n) complexity.

``````#include<stdio.h>
#include<stdlib.h>

typedef struct List* List;
struct List {
int val;
List next;
};

List reverse(List list) { /* with recursion and one static variable*/
static List tail;
if(!list || !list->next) {
tail = list;

return tail;
} else {
reverse1(list->next);
list->next->next = list;
list->next = NULL;

return tail;
}
}
``````
Score: 0

Using two pointers while maintaining time 4 complexity of O(n), the fastest achievable, might 3 only be possible through number casting 2 of pointers and swapping their values. Here 1 is an implementation:

``````#include <stdio.h>

typedef struct node
{
int num;
struct node* next;
}node;

{
node* ptr;
while(ptr)
{
/* Swap head->next and ptr. */

/* Swap head->next->next and ptr. */
}
}

{
while(ptr->next) ptr = ptr->next;
ptr->next = malloc(sizeof(node));
ptr->next->num = n;
ptr->next->next = NULL;
}

void print(node* ptr)
{
while(ptr = ptr->next) printf("%d ", ptr->num);
putchar('\n');
}

void erase(node* ptr)
{
node *end;
while(ptr->next)
{
if(ptr->next->next) ptr = ptr->next;
else
{
end = ptr->next;
ptr->next = NULL;
free(end);
}
}
}

void main()
{
int i, n = 5;
}
``````
Score: 0

I have a slightly different approach. I 7 wanted to make use of the existing functions 6 (like insert_at(index), delete_from(index)) to 5 reverse the list (something like a right 4 shift operation). The complexity is still 3 O(n) but the advantage is more reused code. Have 2 a look at another_reverse() method and let 1 me know what you all think.

``````#include <stdio.h>
#include <stdlib.h>

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

void printList(char* msg) {

printf("\n%s\n", msg);

while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
}

void insert_beginning(int data) {
struct node* newNode = (struct node*) malloc(sizeof(struct node));

newNode->data = data;
newNode->next = NULL;

{
} else {
}
}

void insert_at(int data, int location) {

struct node* newNode = (struct node*) malloc(sizeof(struct node));

newNode->data = data;
newNode->next = NULL;

{
}

else {
int index = 0;

while (currentNode != NULL && index < (location - 1)) {
currentNode = currentNode->next;
index++;
}

if (currentNode != NULL)
{
if (location == 0) {
newNode->next = currentNode;
} else {
newNode->next = currentNode->next;
currentNode->next = newNode;
}
}
}
}

int delete_from(int location) {

int retValue = -1;

if (location < 0 || head == NULL)
{
printf("\nList is empty or invalid index");
return -1;
} else {

int index = 0;

while (currentNode != NULL && index < (location - 1)) {
currentNode = currentNode->next;
index++;
}

if (currentNode != NULL)
{
// we've reached the node just one prior to the one we want to delete

if (location == 0) {

if (currentNode->next == NULL)
{
// this is the only node in the list
retValue = currentNode->data;
free(currentNode);
} else {

// the next node should take its place
struct node* nextNode = currentNode->next;
retValue = currentNode->data;
free(currentNode);
}
} // if (location == 0)
else {
// the next node should take its place
struct node* nextNode = currentNode->next;
currentNode->next = nextNode->next;

if (nextNode != NULL
) {
retValue = nextNode->data;
free(nextNode);
}
}

} else {
printf("\nInvalid index");
return -1;
}
}

return retValue;
}

void another_reverse() {
{
printf("\nList is empty\n");
return;
} else {
// get the tail pointer

int index = 0, counter = 0;

while (tailNode->next != NULL) {
tailNode = tailNode->next;
index++;
}

// now tailNode points to the last node
while (counter != index) {
int data = delete_from(index);
insert_at(data, counter);
counter++;
}
}
}

int main(int argc, char** argv) {

insert_beginning(4);
insert_beginning(3);
insert_beginning(2);
insert_beginning(1);
insert_beginning(0);

/*  insert_at(5, 0);
insert_at(4, 1);
insert_at(3, 2);
insert_at(1, 1);*/

printList("Original List\0");

//reverse_list();
another_reverse();

printList("Reversed List\0");

/*  delete_from(2);
delete_from(2);*/

//printList();
return 0;
}
``````
Score: 0
``````using 2-pointers....bit large but simple and efficient

void reverse()

{

int n=0;

node *temp,*temp1;

temp=strptr;

while(temp->next!=NULL)

{

n++;      //counting no. of nodes

temp=temp->next;

}
// we will exchange ist by last.....2nd by 2nd last so.on....
int i=n/2;

temp=strptr;

for(int j=1;j<=(n-i+1);j++)

temp=temp->next;
//  i started exchanging from in between ....so we do no have to traverse list so far //again and again for exchanging

while(i>0)

{

temp1=strptr;

for(int j=1;j<=i;j++)//this loop for traversing nodes before n/2

temp1=temp1->next;

int t;

t=temp1->info;

temp1->info=temp->info;

temp->info=t;

i--;

temp=temp->next;

//at the end after exchanging say 2 and 4 in a 5 node list....temp will be at 5 and we will traverse temp1 to ist node and exchange ....

}

}
``````

0

Score: 0
``````#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct node
{
int data;
};
struct node *first=NULL,*last=NULL,*next,*pre,*cur,*temp;
void create()
{
cur=(struct node*) malloc(sizeof(struct node));
printf("enter first data to insert");
scanf("%d",&cur->data);
first=last=cur;
}
void insert()
{
int pos,c;
cur=(struct node*) malloc(sizeof(struct node));
printf("enter data to insert and also its position");
scanf("%d%d",&cur->data,&pos);
if(pos==1)
{
first=cur;
}
else
{
c=1;
next=first;
while(c<pos)
{
pre=next;
c++;
}
if(pre==NULL)
{
printf("Invalid position");
}
else
{
}
}
}
void display()
{
cur=first;
while(cur!=NULL)
{
}
printf("\n");
}
void rev()
{
pre=NULL;
cur=first;
while(cur!=NULL)
{
pre=cur;
cur=next;
}
first=pre;
}
void main()
{
int choice;
clrscr();
do
{
printf("Options are: -\n1:Create\n2:Insert\n3:Display\n4:Reverse\n0:Exit\n");
scanf("%d",&choice);
switch(choice)
{
case 1:
create();
break;
case 2:
insert();
break;
case 3:
display();
break;
case 4:
rev();
break;
case 0:
exit(0);
default:
printf("wrong choice");
}
}
while(1);
}
``````

0

Score: 0

Here is my version:

``````void reverse(ListElem *&head)
{
ListElem* temp;

while(temp = elem->next())
{
elem->next(prev);
prev = elem;
elem = temp;
}
elem->next(prev);
}
``````

where

``````class ListElem{
public:
ListElem(int val): _val(val){}
ListElem *next() const { return _next; }
void next(ListElem *elem) { _next = elem; }
void val(int val){ _val = val; }
int val() const { return _val;}
private:
ListElem *_next;
int _val;
};
``````

0

Score: 0

I am using java to implement this and approach 8 is test driven development hence test cases 7 are also attached.

The Node class that represent 6 single node -

``````package com.adnan.linkedlist;

/**
* Date  : 9/21/13
* Time  : 12:02 PM
*/
public class Node {

public Node(int value, Node node){
this.value = value;
this.node = node;
}
private int value;
private Node node;

public int getValue() {
return value;
}

public Node getNode() {
return node;
}

public void setNode(Node node){
this.node = node;
}
}
``````

Service class that takes start 5 node as input and reserve it without using 4 extra space.

``````package com.adnan.linkedlist;

/**
* Date  : 9/21/13
* Time  : 11:54 AM
*/

return service;
}

public Node reverse(Node start){
return start;
}
Node firstNode, secondNode, thirdNode;
firstNode = start;
secondNode = firstNode.getNode();
while (secondNode != null ){
thirdNode = secondNode.getNode();
secondNode.setNode(firstNode);
firstNode = secondNode;
secondNode = thirdNode;
}
start.setNode(null);
return firstNode;
}

return start.getNode() == null;
}

}
``````

And The test case that covers 3 above scenario. Please note that you require 2 junit jars. I am using testng.jar; you can 1 use any whatever pleases you..

``````package com.adnan.linkedlist;

import org.testng.annotations.Test;

import static org.testng.AssertJUnit.assertTrue;

/**
* Date  : 9/21/13
* Time  : 12:11 PM
*/

@Test
public void test_reverseSingleElement() throws Exception {
Node node = new Node(1, null);
reversalService.reverse(node);
assertTrue(node.getNode() == null);
assertTrue(node.getValue() == 1);
}

//original - Node1(1) -> Node2(2) -> Node3(3)
//reverse - Node3(3) -> Node2(2) -> Node1(1)
@Test
public void test_reverseThreeElement() throws Exception {
Node node3 = new Node(3, null);
Node node2 = new Node(2, node3);
Node start = new Node(1, node2);

start = reversalService.reverse(start);
Node test = start;
for (int i = 3; i >=1 ; i -- ){
assertTrue(test.getValue() == i);
test = test.getNode();
}

}

@Test
public void test_reverseFourElement() throws Exception {
Node node4 = new Node(4, null);
Node node3 = new Node(3, node4);
Node node2 = new Node(2, node3);
Node start = new Node(1, node2);

start = reversalService.reverse(start);
Node test = start;
for (int i = 4; i >=1 ; i -- ){
assertTrue(test.getValue() == i);
test = test.getNode();
}
}

@Test
public void test_reverse10Element() throws Exception {
Node node10 = new Node(10, null);
Node node9 = new Node(9, node10);
Node node8 = new Node(8, node9);
Node node7 = new Node(7, node8);
Node node6 = new Node(6, node7);
Node node5 = new Node(5, node6);
Node node4 = new Node(4, node5);
Node node3 = new Node(3, node4);
Node node2 = new Node(2, node3);
Node start = new Node(1, node2);

start = reversalService.reverse(start);
Node test = start;
for (int i = 10; i >=1 ; i -- ){
assertTrue(test.getValue() == i);
test = test.getNode();
}

}

@Test
public void test_reverseTwoElement() throws Exception {
Node node2 = new Node(2, null);
Node start = new Node(1, node2);

start = reversalService.reverse(start);
Node test = start;
for (int i = 2; i >=1 ; i -- ){
assertTrue(test.getValue() == i);
test = test.getNode();
}

}
}
``````
Score: 0

As an alternative, you can use recursion-

``````struct node* reverseList(struct node *head)
{

struct node* remaining = reverseList(second);

return remaining;
}
``````

0

Score: 0

Yes there is a way using only two pointers. That 5 is by creating new linked list where the 4 first node is the first node of the given 3 list and second node of the first list is 2 added at the start of the new list and so 1 on.

Score: 0

A simple algorithm if you use the linked 8 list as a stack structure:

`````` #include <stdio.h>
#include <stdlib.h>

typedef struct list {
int key;
char value;
struct list* next;
} list;
void print(list*);
void reverse(list**);
void deleteList(list*);

int main(void) {
int i=0;
printf("Before reverse: \n");
printf("After reverse: \n");

}
void deleteList(list* l) {

list* t = l;
while ( t != NULL ) {
list* tmp = t;
t = t->next;
free(tmp);
}

}
void print(list* l) {
list* t = l;
while ( t != NULL) {
printf("%d:%c\n", t->key, t->value);
t = t->next;
}
}

list* reversed = NULL;
while ( tmp != NULL ) {
tmp = tmp->next;
}
}

list* t = calloc(1, sizeof(list));
t->key = k; t->value = v;

}
``````

The performance 7 may be affected since additional function 6 call to the add and malloc so the algorithms 5 of address swaps are better but that one 4 actually creates new list so you can use 3 additional options like sort or remove items 2 if you add a callback function as parameter 1 to the reverse.

Score: 0

Here is a slightly different, but simple 1 approach in C++11:

``````#include <iostream>

struct Node{
Node(): next(NULL){}
Node *next;
std::string data;
};

void printlist(Node* l){
while(l){
std::cout<<l->data<<std::endl;
l = l->next;
}
std::cout<<"----"<<std::endl;
}

void reverse(Node*& l)
{
Node* prev = NULL;
while(l){
auto next = l->next;
l->next = prev;
prev=l;
l=next;
}
l = prev;
}

int main() {
Node s,t,u,v;
s.data = "1";
t.data = "2";
u.data = "3";
v.data = "4";
s.next = &t;
t.next = &u;
u.next = &v;
Node* ptr = &s;
printlist(ptr);
reverse(ptr);
printlist(ptr);
return 0;
}
``````

Output here

Score: 0

Following is one implementation using 2 1 pointers (head and r)

``````ListNode * reverse(ListNode* head) {

ListNode *r = NULL;

}

while(r) {

}
}
``````
Score: 0
``````class Node {
Node next;
int data;

Node(int item) {
data = item;
next = null;
}
}

public static void printList(Node node){

while(node!=null){
System.out.print(node.data+" ");
node = node.next;
}
System.out.println();
}

public static Node reverse(Node node){

Node new_node = null;

while(node!=null){

Node next = node.next;
node.next = new_node;
new_node = node;
node = next;

}
return new_node;
}

public static void main(String[] args) {

}

}
``````

0

Score: 0

You can simply reverse a Linked List using 13 only one Extra pointer. And the key to do 12 this is by using a Recursion.

Here is the 11 program in Java.

``````public class Node {
public int data;
public Node next;
}

if (p.next == null) {
q = p;
return q;
} else {
p.next = null;
q.next = p;
q = p;
}
}

// call this function from your main method.
``````

As you can see this is a 10 simple example of a head recursion. We have 9 mainly two different kinds of Recursion.

1. Head Recursion:- When the Recursion is the first thing executed by a function.
2. Tail Recursion:- When the Recursion is the last thing executed by a function.

Here 8 the program will keep calling itself Recursively 7 until our Pointer "p" reaches 6 to the last node and then before returning 5 the stack frame we will point head to the 4 last node and the extra Pointer "q" to 3 build the linked list in the backward direction.

Here 2 the Stack Frames will keep on returning 1 until the stack is empty.

Score: 0

Here's a simpler version in python. It does 1 use only two pointers `slow` & `fast`

``````def reverseList(head: ListNode) -> ListNode:

slow = None
while fast:
node_next = fast.next

fast.next = slow
slow = fast

fast = node_next
return slow
``````
Score: 0

Just use an XOR linked list, which is "naturally reversible" in 3 constant time, by just swapping the first 2 and last (head and tail) pointers.

``````void reverse() noexcept { std::swap(first_, last_); }
``````

Here's 1 a working example.

Score: 0

here is a little simple solution...

``````void reverse()
{
if(pointer1 != NULL)
{
node *pointer2 = pointer1->next;

if(pointer2 != NULL)
{

while(pointer2 != NULL)
{
pointer1 = pointer2;
pointer2 = pointer2->next;