blocks|key|1396624|text|是。我相信你可以用you+can+swap+two+numbers+without+using+a+third同样的方法做到这一点。只需将指针转换为int/long，然后执行几次XOR操作。这是一个有趣的问题的C技巧之一，但没有任何实际价值。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1396625|你能降低O(n)复杂度吗？不，不是真的。如果您认为需要相反的顺序，只需使用双向链表即可。|1396626|entityMap|0|LINK|mutability|MUTABLE|url|https://stackoverflow.com/questions/756750/swap-the-values-of-two-variables-without-using-third-variable^0|9|1A|0|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@$A|O|B|P|1|Q]]|C|$]]|$1|D|3|E|5|6|7|R|8|@]|9|@]|C|$]]|$1|F|3|-4|5|6|7|S|8|@]|9|@]|C|$]]]|G|$H|$5|I|J|K|C|$L|M]]]]

Yes. I'm sure you can do this the same way <a href="https://stackoverflow.com/questions/756750/swap-the-values-of-two-variables-without-using-third-variable">you can swap two numbers without using a third</a>. 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.

blocks|key|1181224|text|计算出你现在使用的算法的时间复杂度，很明显它是不能改进的。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1181225|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

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

blocks|key|1396738|text|还有别的选择吗？不，这就像它得到的一样简单，并且没有根本不同的方法。这个算法已经是O(n)时间了，你不能再快了，因为你必须修改每个节点。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1396739|看起来你的代码是在正确的轨道上，但是它在上面的形式中并不能很好地工作。下面是一个工作版本：|1396740|#include+<stdio.h>

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

void+print_list(Node*+root)+{
++while+(root)+{
++++printf("%25c+",+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;
}|code-block|syntax|javascript|1396741|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|L|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|M|8|@]|9|@]|A|$G|H]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

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:

<pre><code>#include &lt;stdio.h&gt;

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

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

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

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

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

 return 0;
}
</code></pre>

blocks|key|1181325|text|不，不能做比当前O(n)更快的事情。您需要更改每个节点，因此时间将与元素的数量成正比，这是您已经拥有的O(n)。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1181326|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

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.

blocks|key|1181402|text|只是为了好玩(尽管尾递归优化应该会阻止它吃掉所有堆栈)：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1181403|Node*+reverse+(Node+*root,+Node+*end)+{

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

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

root+=+reverse(root,+NULL);|code-block|syntax|javascript|1181404|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

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

<pre><code>
Node* reverse (Node *root, Node *end) {

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

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

root = reverse(root, NULL);
</code></pre>

blocks|key|1396839|text|可读性更好的：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1396840|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);
}|code-block|syntax|javascript|1396841|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

How about the more readable:

<pre><code>
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);
}
</code></pre>

blocks|key|1181459|text|#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;
}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|1181460|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre><code>#include &lt;stddef.h&gt;

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

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

blocks|key|1181527|text|你只需要一个额外的指针就可以解决这个问题，这个额外的指针对于反向函数来说必须是静态的。复杂度为O(n)。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1181528|#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+%7C%7C+!list->next)+{
++++++++tail+=+list;

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

++++++++return+tail;
++++}
}|code-block|syntax|javascript|1181529|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

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

<pre><code>#include&lt;stdio.h&gt;
#include&lt;stdlib.h&gt;

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-&gt;next) {
 tail = list;

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

 return tail;
 }
}
</code></pre>

blocks|key|1396996|text|使用两个指针，同时保持O(n)的时间复杂度，这是最快的，可能只能通过指针的数字转换和交换它们的值来实现。下面是一个实现：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1396997|#include+<stdio.h>

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

void+reverse(node*+head)
{
+++node*+ptr;
+++if(!head+%7C%7C+!head->next+%7C%7C+!head->next->next)+return;
+++ptr+=+head->next->next;
+++head->next->next+=+NULL;
+++while(ptr)
+++{
+++++/*+Swap+head->next+and+ptr.+*/
+++++head->next+=+(unsigned)(ptr+=\
+++++(unsigned)ptr+%5E+(unsigned)(head->next+=\
+++++(unsigned)head->next+%5E+(unsigned)ptr))+%5E+(unsigned)head->next;

+++++/*+Swap+head->next->next+and+ptr.+*/
+++++head->next->next+=+(unsigned)(ptr+=\
+++++(unsigned)ptr+%5E+(unsigned)(head->next->next+=\
+++++(unsigned)head->next->next+%5E+(unsigned)ptr))+%5E+(unsigned)head->next->next;
+++}
}

void+add_end(node*+ptr,+int+n)
{
++++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("%25d+",+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;
++++node*+dummy_head;
++++dummy_head->next+=+NULL;
++++for(i+=+1;+i+<=+n+;+%2B%2Bi)+add_end(dummy_head,+i);
++++print(dummy_head);
++++reverse(dummy_head);
++++print(dummy_head);
++++erase(dummy_head);
}|code-block|syntax|javascript|1396998|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

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

<pre><code>#include &lt;stdio.h&gt;

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

void reverse(node* head)
{
 node* ptr;
 if(!head || !head-&gt;next || !head-&gt;next-&gt;next) return;
 ptr = head-&gt;next-&gt;next;
 head-&gt;next-&gt;next = NULL;
 while(ptr)
 {
 /* Swap head-&gt;next and ptr. */
 head-&gt;next = (unsigned)(ptr =\
 (unsigned)ptr ^ (unsigned)(head-&gt;next =\
 (unsigned)head-&gt;next ^ (unsigned)ptr)) ^ (unsigned)head-&gt;next;

 /* Swap head-&gt;next-&gt;next and ptr. */
 head-&gt;next-&gt;next = (unsigned)(ptr =\
 (unsigned)ptr ^ (unsigned)(head-&gt;next-&gt;next =\
 (unsigned)head-&gt;next-&gt;next ^ (unsigned)ptr)) ^ (unsigned)head-&gt;next-&gt;next;
 }
}

void add_end(node* ptr, int n)
{
 while(ptr-&gt;next) ptr = ptr-&gt;next;
 ptr-&gt;next = malloc(sizeof(node));
 ptr-&gt;next-&gt;num = n;
 ptr-&gt;next-&gt;next = NULL;
}

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

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

void main()
{
 int i, n = 5;
 node* dummy_head;
 dummy_head-&gt;next = NULL;
 for(i = 1; i &lt;= n ; ++i) add_end(dummy_head, i);
 print(dummy_head);
 reverse(dummy_head);
 print(dummy_head);
 erase(dummy_head);
}
</code></pre>

blocks|key|1181652|text|我有一个稍微不同的方法。我想利用现有的函数(如insert_at(索引)，delete_from(索引))来反转列表(类似于右移位操作)。复杂度仍然是O(n)，但优点是更多的代码被重用。看看another_reverse()方法，让我知道你们的想法。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1181653|#include+<stdio.h>
#include+<stdlib.h>

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

struct+node*+head+=+NULL;

void+printList(char*+msg)+{
++++struct+node*+current+=+head;

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

++++while+(current+!=+NULL)+{
++++++++printf("%25d+",+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;

++++if+(head+==+NULL)
++++{
++++++++head+=+newNode;
++++}+else+{
++++++++newNode->next+=+head;
++++++++head+=+newNode;
++++}
}

void+insert_at(int+data,+int+location)+{

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

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

++++if+(head+==+NULL)
++++{
++++++++head+=+newNode;
++++}

++++else+{
++++++++struct+node*+currentNode+=+head;
++++++++int+index+=+0;

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

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


int+delete_from(int+location)+{

++++int+retValue+=+-1;

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

++++++++struct+node*+currentNode+=+head;
++++++++int+index+=+0;

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

++++++++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);
++++++++++++++++++++head+=+NULL;
++++++++++++++++}+else+{

++++++++++++++++++++//+the+next+node+should+take+its+place
++++++++++++++++++++struct+node*+nextNode+=+currentNode->next;
++++++++++++++++++++head+=+nextNode;
++++++++++++++++++++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()+{
++++if+(head+==+NULL)
++++{
++++++++printf("\nList+is+empty\n");
++++++++return;
++++}+else+{
++++++++//+get+the+tail+pointer

++++++++struct+node*+tailNode+=+head;
++++++++int+index+=+0,+counter+=+0;

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

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

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;
}|code-block|syntax|javascript|1181654|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

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

<pre><code>#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;

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

struct node* head = NULL;

void printList(char* msg) {
 struct node* current = head;

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

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

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

 newNode-&gt;data = data;
 newNode-&gt;next = NULL;

 if (head == NULL)
 {
 head = newNode;
 } else {
 newNode-&gt;next = head;
 head = newNode;
 }
}

void insert_at(int data, int location) {

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

 newNode-&gt;data = data;
 newNode-&gt;next = NULL;

 if (head == NULL)
 {
 head = newNode;
 }

 else {
 struct node* currentNode = head;
 int index = 0;

 while (currentNode != NULL &amp;&amp; index &lt; (location - 1)) {
 currentNode = currentNode-&gt;next;
 index++;
 }

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


int delete_from(int location) {

 int retValue = -1;

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

 struct node* currentNode = head;
 int index = 0;

 while (currentNode != NULL &amp;&amp; index &lt; (location - 1)) {
 currentNode = currentNode-&gt;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-&gt;next == NULL)
 {
 // this is the only node in the list
 retValue = currentNode-&gt;data;
 free(currentNode);
 head = NULL;
 } else {

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

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

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

 return retValue;
}

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

 struct node* tailNode = head;
 int index = 0, counter = 0;

 while (tailNode-&gt;next != NULL) {
 tailNode = tailNode-&gt;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;
}
</code></pre>

blocks|key|1397069|text|using+2-pointers....bit+large+but+simple+and+efficient

void+reverse()

{

int+n=0;

node+*temp,*temp1;

temp=strptr;

while(temp->next!=NULL)

{

n%2B%2B;++++++//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%2B1);j%2B%2B)

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%2B%2B)//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+....

}

}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|1397070|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre><code>using 2-pointers....bit large but simple and efficient

void reverse()

{

int n=0;

node *temp,*temp1;

temp=strptr;

while(temp-&gt;next!=NULL)

{

n++; //counting no. of nodes

temp=temp-&gt;next;

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

temp=strptr;

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

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

while(i&gt;0)

{

temp1=strptr;

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

temp1=temp1-&gt;next;

int t;

t=temp1-&gt;info;

temp1-&gt;info=temp-&gt;info;

temp-&gt;info=t;

i--;

temp=temp-&gt;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 ....

}

}
</code></pre>

blocks|key|1181675|text|#include+<stdio.h>
#include+<malloc.h>

tydef+struct+node
{
++++int+info;
++++struct+node+*link;
}+*start;

void+main()
{
++++rev();
}

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

++++start+=+q;
}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|1181676|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre><code>#include &lt;stdio.h&gt;
#include &lt;malloc.h&gt;

tydef struct node
{
 int info;
 struct node *link;
} *start;

void main()
{
 rev();
}

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

 start = q;
}
</code></pre>

blocks|key|1397123|text|你可以使用递归方法：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1397124|下面是伪代码：|1397125|Node*+reverse(Node*+root)
{
++++if(!root)+return+NULL;

++++if(!(root->next))+temp+=+root;
++++else
++++{
++++++++reverse(root->next);
++++++++root->next->next+=+root;
++++++++root->next+=+NULL;
++++}

++++return+temp;
}|code-block|syntax|javascript|1397126|调用函数后，它将返回链表的新根temp。因为很明显它只使用了两个指针。|offset|length|style|CODE|1397127|entityMap^0|0|0|0|F|4|0^^$0|@$1|2|3|4|5|6|7|Q|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|R|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|S|8|@]|9|@]|A|$G|H]]|$1|I|3|J|5|6|7|T|8|@$K|U|L|V|M|N]]|9|@]|A|$]]|$1|O|3|-4|5|6|7|W|8|@]|9|@]|A|$]]]|P|$]]

You can go for recursive approach:

Here is the pseudo code:

<pre><code>Node* reverse(Node* root)
{
 if(!root) return NULL;

 if(!(root-&gt;next)) temp = root;
 else
 {
 reverse(root-&gt;next);
 root-&gt;next-&gt;next = root;
 root-&gt;next = NULL;
 }

 return temp;
}
</code></pre>

After the call is made to the function, it returns the new root[<code>temp</code>] of the linked list.
As it is very clear that it makes use of only two pointers.

blocks|key|1181734|text|//with+this+no+extra+space+and+no+extra+scans+but+this+code+is+reversing+code+but+read
//+in+reverse+direction+no+changes+made+in+the+linked+list+
PrintInReverse(Node+node)
{
+++//+given+list+is+null
+++if(node+==null)
+++++++return+null;
+++//+if+list+contains+only+one+node
+++if(node->next+==null)
+++{
+++++++print(node.value)
+++}
+++//+call+recursively+
+++else
+++{
+++++++//while(node->next+!=+null)//+due+to+while+loop+it+goes+into+infinite+loop.use+//if
+++++++if(node->next!=NULL)
+++++++{
+++++++++++PrintInReverse(node->next)
+++++++++++print(node.value)
+++++++}
+++}
}

Add+comments...|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|1181735|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre><code>//with this no extra space and no extra scans but this code is reversing code but read
// in reverse direction no changes made in the linked list 
PrintInReverse(Node node)
{
 // given list is null
 if(node ==null)
 return null;
 // if list contains only one node
 if(node-&gt;next ==null)
 {
 print(node.value)
 }
 // call recursively 
 else
 {
 //while(node-&gt;next != null)// due to while loop it goes into infinite loop.use //if
 if(node-&gt;next!=NULL)
 {
 PrintInReverse(node-&gt;next)
 print(node.value)
 }
 }
}

Add comments...
</code></pre>

blocks|key|1397140|text|#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct+node
{
int+data;
struct+node+*link;
};
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("%25d",&cur->data);
first=last=cur;
first->link=NULL;
}
void+insert()
{
int+pos,c;
cur=(struct+node*)+malloc(sizeof(struct+node));
printf("enter+data+to+insert+and+also+its+position");
scanf("%25d%25d",&cur->data,&pos);
if(pos==1)
{
cur->link=first;
first=cur;
}
else
{
c=1;
++++next=first;
++++while(c<pos)
++++{
++++++++pre=next;
++++++++next=next->link;
++++++++c%2B%2B;
++++}
++++++++if(pre==NULL)
++++++++{
++++++++++++printf("Invalid+position");
++++++++}
++++++++else
++++++++{
++++++++cur->link=pre->link;
++++++++pre->link=cur;
++++++++}
}
}
void+display()
{
cur=first;
while(cur!=NULL)
{
printf("data=+%25d\t+address=+%25u\n",cur->data,cur);
cur=cur->link;
}
printf("\n");
}
void+rev()
{
pre=NULL;
cur=first;
while(cur!=NULL)
{
next=cur->link;
cur->link=pre;
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");
printf("Enter+your+choice:+-+");
scanf("%25d",&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);
}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|1397141|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre><code>#include&lt;stdio.h&gt;
#include&lt;conio.h&gt;
#include&lt;stdlib.h&gt;
struct node
{
int data;
struct node *link;
};
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",&amp;cur-&gt;data);
first=last=cur;
first-&gt;link=NULL;
}
void insert()
{
int pos,c;
cur=(struct node*) malloc(sizeof(struct node));
printf("enter data to insert and also its position");
scanf("%d%d",&amp;cur-&gt;data,&amp;pos);
if(pos==1)
{
cur-&gt;link=first;
first=cur;
}
else
{
c=1;
 next=first;
 while(c&lt;pos)
 {
 pre=next;
 next=next-&gt;link;
 c++;
 }
 if(pre==NULL)
 {
 printf("Invalid position");
 }
 else
 {
 cur-&gt;link=pre-&gt;link;
 pre-&gt;link=cur;
 }
}
}
void display()
{
cur=first;
while(cur!=NULL)
{
printf("data= %d\t address= %u\n",cur-&gt;data,cur);
cur=cur-&gt;link;
}
printf("\n");
}
void rev()
{
pre=NULL;
cur=first;
while(cur!=NULL)
{
next=cur-&gt;link;
cur-&gt;link=pre;
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");
printf("Enter your choice: - ");
scanf("%d",&amp;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);
}
</code></pre>

blocks|key|1397192|text|在不使用临时变量的情况下交换两个变量，|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1397193|a+=+a+xor+b
b+=+a+xor+b
a+=+a+xor+b|code-block|syntax|javascript|1397194|最快的方法是在一行中编写它|1397195|a+=+a+%5E+b+%5E+(b=a)|1397196|类似地，|1397197|使用两个交换|1397198|swap(a,b)
swap(b,c)|1397199|使用xor的解决方案|1397200|a+=+a%5Eb%5Ec
b+=+a%5Eb%5Ec
c+=+a%5Eb%5Ec
a+=+a%5Eb%5Ec|1397201|一行解决方案|1397202|c+=+a+%5E+b+%5E+c+%5E+(a=b)+%5E+(b=c)
b+=+a+%5E+b+%5E+c+%5E+(c=a)+%5E+(a=b)
a+=+a+%5E+b+%5E+c+%5E+(b=c)+%5E+(c=a)|1397203|同样的逻辑也用于反转链表。|1397204|typedef+struct+List
{
+int+info;
+struct+List+*next;
}List;


List*+reverseList(List+*head)
{
+p=head;
+q=p->next;
+p->next=NULL;
+while(q)
+{
++++q+=+(List*)+((int)p+%5E+(int)q+%5E+(int)q->next+%5E+(int)(q->next=p)+%5E+(int)(p=q));
+}
+head+=+p;
+return+head;
}++|1397205|entityMap^0|0|0|0|0|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|14|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|15|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|16|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|17|8|@]|9|@]|A|$E|F]]|$1|K|3|L|5|6|7|18|8|@]|9|@]|A|$]]|$1|M|3|N|5|6|7|19|8|@]|9|@]|A|$]]|$1|O|3|P|5|D|7|1A|8|@]|9|@]|A|$E|F]]|$1|Q|3|R|5|6|7|1B|8|@]|9|@]|A|$]]|$1|S|3|T|5|D|7|1C|8|@]|9|@]|A|$E|F]]|$1|U|3|V|5|6|7|1D|8|@]|9|@]|A|$]]|$1|W|3|X|5|D|7|1E|8|@]|9|@]|A|$E|F]]|$1|Y|3|Z|5|6|7|1F|8|@]|9|@]|A|$]]|$1|10|3|11|5|D|7|1G|8|@]|9|@]|A|$E|F]]|$1|12|3|-4|5|6|7|1H|8|@]|9|@]|A|$]]]|13|$]]

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

<pre><code>a = a xor b
b = a xor b
a = a xor b
</code></pre>

fastest way is to write it in one line

<pre><code>a = a ^ b ^ (b=a)
</code></pre>

Similarly,

using two swaps

<pre><code>swap(a,b)
swap(b,c)
</code></pre>

solution using xor

<pre><code>a = a^b^c
b = a^b^c
c = a^b^c
a = a^b^c
</code></pre>

solution in one line

<pre><code>c = a ^ b ^ c ^ (a=b) ^ (b=c)
b = a ^ b ^ c ^ (c=a) ^ (a=b)
a = a ^ b ^ c ^ (b=c) ^ (c=a)
</code></pre>

The same logic is used to reverse a linked list.

<pre><code>typedef struct List
{
 int info;
 struct List *next;
}List;


List* reverseList(List *head)
{
 p=head;
 q=p-&gt;next;
 p-&gt;next=NULL;
 while(q)
 {
 q = (List*) ((int)p ^ (int)q ^ (int)q-&gt;next ^ (int)(q-&gt;next=p) ^ (int)(p=q));
 }
 head = p;
 return head;
} 
</code></pre>

blocks|key|1181786|text|这是reverse+a+singly+linked+list+in+C的代码。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1181787|这里是粘贴在下面的：|1181788|//+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("[%25d]->",+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
//+++%7C++++%7C++++%7C
//+++v++++v++++v
//+NULL++[0]->[1]->[2]->NULL
//
//+Step+2:
//
//++++++prev+head++next
//++++++++%7C++++%7C++++%7C
//++++++++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;
}|code-block|syntax|javascript|1181789|entityMap|0|LINK|mutability|MUTABLE|url|https://gist.github.com/mattdipasquale/4751900^0|2|X|0|0|0|0^^$0|@$1|2|3|4|5|6|7|S|8|@]|9|@$A|T|B|U|1|V]]|C|$]]|$1|D|3|E|5|6|7|W|8|@]|9|@]|C|$]]|$1|F|3|G|5|H|7|X|8|@]|9|@]|C|$I|J]]|$1|K|3|-4|5|6|7|Y|8|@]|9|@]|C|$]]]|L|$M|$5|N|O|P|C|$Q|R]]]]

Here's the code to <a href="https://gist.github.com/mattdipasquale/4751900">reverse a singly linked list in C</a>.

And here it is pasted below:

<pre><code>// reverse.c

#include &lt;stdio.h&gt;
#include &lt;assert.h&gt;

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]-&gt;", head-&gt;data);
 head = head-&gt;next;
 }
 printf("NULL\n");
}

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

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

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

 printf("Passed!");
}

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

 while (head) {
 next = head-&gt;next;
 head-&gt;next = prev;
 prev = head;
 head = next;
 }

 return prev;
}
</code></pre>

blocks|key|1181808|text|这里有一个小的简单的解决方案。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1181809|void+reverse()
{
++++node+*+pointer1+=+head->next;
++++if(pointer1+!=+NULL)
++++{
++++++++node+*pointer2+=+pointer1->next;
++++++++pointer1->next+=+head;
++++++++head->next+=+NULL;
++++++++head+=+pointer1;

++++++++if(pointer2+!=+NULL)
++++++++{

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

++++++++++++pointer1->next+=+head;
++++++++++++head+=+pointer1;
++++++++}+++++++
+++}
+}|code-block|syntax|javascript|1181810|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

here is a little simple solution...

<pre><code>void reverse()
{
 node * pointer1 = head-&gt;next;
 if(pointer1 != NULL)
 {
 node *pointer2 = pointer1-&gt;next;
 pointer1-&gt;next = head;
 head-&gt;next = NULL;
 head = pointer1;

 if(pointer2 != NULL)
 {

 while(pointer2 != NULL)
 {
 pointer1 = pointer2;
 pointer2 = pointer2-&gt;next;
 pointer1-&gt;next = head;
 head = pointer1;
 }

 pointer1-&gt;next = head;
 head = pointer1;
 } 
 }
 }
</code></pre>

blocks|key|1181945|text|是的，有一种方法只使用两个指针。也就是说，通过创建新的链表，其中第一个节点是给定列表的第一个节点，并且将第一个列表的第二个节点添加到新列表的开头，依此类推。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1181946|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

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

blocks|key|1397443|text|以下是我的版本：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1397444|void+reverse(ListElem+*&head)
{
++++ListElem*+temp;
++++ListElem*+elem+=+head->next();
++++ListElem*+prev+=+head;
++++head->next(0);

++++while(temp+=+elem->next())
++++{
++++++++elem->next(prev);
++++++++prev+=+elem;
++++++++elem+=+temp;
++++}
++++elem->next(prev);
++++head+=+elem;
}|code-block|syntax|javascript|1397445|哪里|1397446|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;
};|1397447|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|N|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|O|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|P|8|@]|9|@]|A|$E|F]]|$1|K|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|L|$]]

Here is my version:

<pre><code>void reverse(ListElem *&amp;head)
{
 ListElem* temp;
 ListElem* elem = head-&gt;next();
 ListElem* prev = head;
 head-&gt;next(0);

 while(temp = elem-&gt;next())
 {
 elem-&gt;next(prev);
 prev = elem;
 elem = temp;
 }
 elem-&gt;next(prev);
 head = elem;
}
</code></pre>

where

<pre><code>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;
};
</code></pre>

blocks|key|1397479|text|我正在使用java来实现这一点，方法是测试驱动开发，因此也附加了测试用例。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1397480|表示单个节点Node类-|1397481|package+com.adnan.linkedlist;

/**
+*+User++:+Adnan
+*+Email+:+sendtoadnan@gmail.com
+*+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;
++++}
}|code-block|syntax|javascript|1397482|将起始节点作为输入并保留它而不使用额外空间的服务类。|1397483|package+com.adnan.linkedlist;

/**
+*+User++:+Adnan
+*+Email+:+sendtoadnan@gmail.com
+*+Date++:+9/21/13
+*+Time++:+11:54+AM
+*/
public+class+SinglyLinkedListReversal+{

++++private+static+final+SinglyLinkedListReversal+service+
=+new+SinglyLinkedListReversal();
++++public+static+SinglyLinkedListReversal+getService(){
++++++++return+service;
++++}



++++public+Node+reverse(Node+start){
++++++++if+(hasOnlyNodeInLinkedList(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;
++++}

++++private+boolean+hasOnlyNodeInLinkedList(Node+start)+{
++++++++return+start.getNode()+==+null;
++++}


}|1397484|以及涵盖上述场景的测试用例。请注意，您需要junit+jar。我使用的是testng.jar；你可以使用任何你喜欢的东西。|1397485|package+com.adnan.linkedlist;

import+org.testng.annotations.Test;

import+static+org.testng.AssertJUnit.assertTrue;

/**
+*+User++:+Adnan
+*+Email+:+sendtoadnan@gmail.com
+*+Date++:+9/21/13
+*+Time++:+12:11+PM
+*/
public+class+SinglyLinkedListReversalTest+{

++++private+SinglyLinkedListReversal+reversalService+=+
SinglyLinkedListReversal.getService();

++++@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();
++++++++}


++++}
}|1397486|entityMap^0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|S|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|T|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|U|8|@]|9|@]|A|$G|H]]|$1|I|3|J|5|6|7|V|8|@]|9|@]|A|$]]|$1|K|3|L|5|F|7|W|8|@]|9|@]|A|$G|H]]|$1|M|3|N|5|6|7|X|8|@]|9|@]|A|$]]|$1|O|3|P|5|F|7|Y|8|@]|9|@]|A|$G|H]]|$1|Q|3|-4|5|6|7|Z|8|@]|9|@]|A|$]]]|R|$]]

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

The Node class that represent single node -

<pre><code>package com.adnan.linkedlist;

/**
 * User : Adnan
 * Email : sendtoadnan@gmail.com
 * 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;
 }
}
</code></pre>

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

<pre><code>package com.adnan.linkedlist;

/**
 * User : Adnan
 * Email : sendtoadnan@gmail.com
 * Date : 9/21/13
 * Time : 11:54 AM
 */
public class SinglyLinkedListReversal {

 private static final SinglyLinkedListReversal service 
= new SinglyLinkedListReversal();
 public static SinglyLinkedListReversal getService(){
 return service;
 }



 public Node reverse(Node start){
 if (hasOnlyNodeInLinkedList(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;
 }

 private boolean hasOnlyNodeInLinkedList(Node start) {
 return start.getNode() == null;
 }


}
</code></pre>

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

<pre><code>package com.adnan.linkedlist;

import org.testng.annotations.Test;

import static org.testng.AssertJUnit.assertTrue;

/**
 * User : Adnan
 * Email : sendtoadnan@gmail.com
 * Date : 9/21/13
 * Time : 12:11 PM
 */
public class SinglyLinkedListReversalTest {

 private SinglyLinkedListReversal reversalService = 
SinglyLinkedListReversal.getService();

 @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) -&gt; Node2(2) -&gt; Node3(3)
 //reverse - Node3(3) -&gt; Node2(2) -&gt; 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 &gt;=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 &gt;=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 &gt;=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 &gt;=1 ; i -- ){
 assertTrue(test.getValue() == i);
 test = test.getNode();
 }


 }
}
</code></pre>

blocks|key|1397526|text|作为替代，您可以使用递归-|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1397527|struct+node*+reverseList(struct+node+*head)
{
++++if(head+==+NULL)+return+NULL;
++++if(head->next+==+NULL)+return+head;

++++struct+node*+second+=+head->next;+++++++
++++head->next+=+NULL;

++++struct+node*+remaining+=+reverseList(second);
++++second->next+=+head;

++++return+remaining;
}|code-block|syntax|javascript|1397528|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

As an alternative, you can use recursion-

<pre><code>struct node* reverseList(struct node *head)
{
 if(head == NULL) return NULL;
 if(head-&gt;next == NULL) return head;

 struct node* second = head-&gt;next; 
 head-&gt;next = NULL;

 struct node* remaining = reverseList(second);
 second-&gt;next = head;

 return remaining;
}
</code></pre>

blocks|key|1182105|text|如果你使用链表作为堆栈结构，一个简单的算法：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1182106|+#include+<stdio.h>
#include+<stdlib.h>

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

int+main(void)+{
++++list*+head+=+NULL;
++++int+i=0;
++++while+(+i%2B%2B+<+26+)+add(&head,+i,+i%2B'a');
++++printf("Before+reverse:+\n");
++++print(head);
++++printf("After+reverse:+\n");
++++reverse(&head);
++++print(head);
++++deleteList(head);

}
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("%25d:%25c\n",+t->key,+t->value);
++++++++t+=+t->next;
++++}
}

void+reverse(list**+head)+{
++++list*+tmp+=+*head;
++++list*+reversed+=+NULL;
++++while+(+tmp+!=+NULL+)+{
++++++++add(&reversed,+tmp->key,+tmp->value);
++++++++tmp+=+tmp->next;
++++}
++++deleteList(*head);
++++*head+=+reversed;
}

void+add(list**+head,+int+k,+char+v)+{

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

}|code-block|syntax|javascript|1182107|性能可能会受到影响，因为额外的函数调用add和malloc，因此地址交换的算法更好，但实际上会创建新的列表，所以如果您将回调函数作为参数添加到反向列表中，则可以使用其他选项，如排序或删除项。|1182108|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|L|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|M|8|@]|9|@]|A|$]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

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

<pre><code> #include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;

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

int main(void) {
 list* head = NULL;
 int i=0;
 while ( i++ &lt; 26 ) add(&amp;head, i, i+'a');
 printf("Before reverse: \n");
 print(head);
 printf("After reverse: \n");
 reverse(&amp;head);
 print(head);
 deleteList(head);

}
void deleteList(list* l) {

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

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

void reverse(list** head) {
 list* tmp = *head;
 list* reversed = NULL;
 while ( tmp != NULL ) {
 add(&amp;reversed, tmp-&gt;key, tmp-&gt;value);
 tmp = tmp-&gt;next;
 }
 deleteList(*head);
 *head = reversed;
}

void add(list** head, int k, char v) {

 list* t = calloc(1, sizeof(list));
 t-&gt;key = k; t-&gt;value = v;
 t-&gt;next = *head;
 *head = t;

}
</code></pre>

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

blocks|key|1182164|text|下面是C%2B%2B11中的一种稍微不同但很简单的方法：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1182165|#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;
}|code-block|syntax|javascript|1182166|输出here|offset|length|1182167|entityMap|0|LINK|mutability|MUTABLE|url|http://ideone.com/pniFpn^0|0|0|2|4|0|0^^$0|@$1|2|3|4|5|6|7|S|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|T|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|U|8|@]|9|@$I|V|J|W|1|X]]|A|$]]|$1|K|3|-4|5|6|7|Y|8|@]|9|@]|A|$]]]|L|$M|$5|N|O|P|A|$Q|R]]]]

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

<pre><code>#include &lt;iostream&gt;

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

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

void reverse(Node*&amp; l)
{
 Node* prev = NULL;
 while(l){
 auto next = l-&gt;next;
 l-&gt;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 = &amp;t;
 t.next = &amp;u;
 u.next = &amp;v;
 Node* ptr = &amp;s;
 printlist(ptr);
 reverse(ptr);
 printlist(ptr);
 return 0;
}
</code></pre>

Output <a href="http://ideone.com/pniFpn" rel="nofollow">here</a>

blocks|key|1397632|text|下面是一个使用两个指针(head和r)的实现|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1397633|ListNode+*+reverse(ListNode*+head)+{

++++ListNode+*r+=+NULL;

++++if(head)+{
++++++++r+=+head->next;
++++++++head->next+=+NULL;
++++}

++++while(r)+{
++++++++head+=+reinterpret_cast<ListNode*>(size_t(head)+%5E+size_t(r->next));
++++++++r->next+=+reinterpret_cast<ListNode*>(size_t(r->next)+%5E+size_t(head));
++++++++head+=+reinterpret_cast<ListNode*>(size_t(head)+%5E+size_t(r->next));

++++++++head+=+reinterpret_cast<ListNode*>(size_t(head)+%5E+size_t(r));
++++++++r+=+reinterpret_cast<ListNode*>(size_t(r)+%5E+size_t(head));
++++++++head+=+reinterpret_cast<ListNode*>(size_t(head)+%5E+size_t(r));
++++}
++++return+head;
}|code-block|syntax|javascript|1397634|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

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

<pre><code>ListNode * reverse(ListNode* head) {

 ListNode *r = NULL;

 if(head) {
 r = head-&gt;next;
 head-&gt;next = NULL;
 }

 while(r) {
 head = reinterpret_cast&lt;ListNode*&gt;(size_t(head) ^ size_t(r-&gt;next));
 r-&gt;next = reinterpret_cast&lt;ListNode*&gt;(size_t(r-&gt;next) ^ size_t(head));
 head = reinterpret_cast&lt;ListNode*&gt;(size_t(head) ^ size_t(r-&gt;next));

 head = reinterpret_cast&lt;ListNode*&gt;(size_t(head) ^ size_t(r));
 r = reinterpret_cast&lt;ListNode*&gt;(size_t(r) ^ size_t(head));
 head = reinterpret_cast&lt;ListNode*&gt;(size_t(head) ^ size_t(r));
 }
 return head;
}
</code></pre>

blocks|key|1182240|text|这里有一个更简单的Java版本。它只使用了两个指针curr和prev|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1182241|public+void+reverse(Node+head)+{
++++Node+curr+=+head,+prev+=+null;

++++while+(head.next+!=+null)+{
++++++++head+=+head.next;+//+move+the+head+to+next+node
++++++++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
++++++++curr+=+head;++++++//+current+moves+along+with+head
++++}

++++head.next+=+prev;+++++//for+last+node
}|code-block|syntax|javascript|1182242|entityMap^0|P|4|U|4|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@$9|N|A|O|B|C]|$9|P|A|Q|B|C]]|D|@]|E|$]]|$1|F|3|G|5|H|7|R|8|@]|D|@]|E|$I|J]]|$1|K|3|-4|5|6|7|S|8|@]|D|@]|E|$]]]|L|$]]

Here's a simpler version in Java. It does use only two pointers <code>curr</code> &amp; <code>prev</code>

<pre><code>public void reverse(Node head) {
 Node curr = head, prev = null;

 while (head.next != null) {
 head = head.next; // move the head to next node
 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
 curr = head; // current moves along with head
 }

 head.next = prev; //for last node
}
</code></pre>

blocks|key|1182283|text|我不明白为什么需要返回head，因为我们将它作为参数传递。我们正在传递链表的头部，然后我们也可以更新。下面是一个简单的解决方案。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1182284|#include<stdio.h>
#include<conio.h>

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

typedef+struct+NODE+node;

void+reverse(node+**head);
void+add_end(node+**head,int+val);
void+alloc(node+**p);
void+print_all(node+*head);

void+main()
{
++++node+*head;
++++clrscr();
++++head+=+NULL;
++++add_end(+&head,+1+);
++++add_end(+&head,+2+);
++++add_end(+&head,+3+);
++++print_all(+head+);
++++reverse(+&head+);
++++print_all(+head+);
++++getch();
}
void+alloc(node+**p)
{
++++node+*temp;
++++temp+=+(node+*)+malloc(+sizeof(node+*)+);
++++temp->next+=+NULL;
++++*p+=+temp;
}
void+add_end(node+**head,int+val)
{
++++node+*temp,*new_node;
++++alloc(&new_node);
++++new_node->value+=+val;
++++if(+*head+==+NULL+)
++++{
++++++++*head+=+new_node;
++++++++return;
++++}
++++for(temp+=+*head;temp->next!=NULL;temp=temp->next);
++++temp->next+=+new_node;
}
void+print_all(node+*head)
{
++++node+*temp;
++++int+index=0;
++++printf+("\n\n");
++++if+(head+==+NULL)
++++{
++++++++printf+("+List+is+Empty+\n");
++++++++return;
++++}
++++for+(temp=head;+temp+!=+NULL;+temp=temp->next,index%2B%2B)
++++++++printf+("+%25d+==>+%25d+\n",index,temp->value);
}
void+reverse(node+**head)
{
++++node+*next,*new_head;
++++new_head=NULL;
++++while(*head+!=+NULL)
++++{
++++++++next+=+(*head)->next;
++++++++(*head)->next+=+new_head;
++++++++new_head+=+(*head);
++++++++(*head)+=+next;
++++}
++++(*head)=new_head;
}|code-block|syntax|javascript|1182285|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

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

<pre><code>#include&lt;stdio.h&gt;
#include&lt;conio.h&gt;

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

typedef struct NODE node;

void reverse(node **head);
void add_end(node **head,int val);
void alloc(node **p);
void print_all(node *head);

void main()
{
 node *head;
 clrscr();
 head = NULL;
 add_end( &amp;head, 1 );
 add_end( &amp;head, 2 );
 add_end( &amp;head, 3 );
 print_all( head );
 reverse( &amp;head );
 print_all( head );
 getch();
}
void alloc(node **p)
{
 node *temp;
 temp = (node *) malloc( sizeof(node *) );
 temp-&gt;next = NULL;
 *p = temp;
}
void add_end(node **head,int val)
{
 node *temp,*new_node;
 alloc(&amp;new_node);
 new_node-&gt;value = val;
 if( *head == NULL )
 {
 *head = new_node;
 return;
 }
 for(temp = *head;temp-&gt;next!=NULL;temp=temp-&gt;next);
 temp-&gt;next = new_node;
}
void print_all(node *head)
{
 node *temp;
 int index=0;
 printf ("\n\n");
 if (head == NULL)
 {
 printf (" List is Empty \n");
 return;
 }
 for (temp=head; temp != NULL; temp=temp-&gt;next,index++)
 printf (" %d ==&gt; %d \n",index,temp-&gt;value);
}
void reverse(node **head)
{
 node *next,*new_head;
 new_head=NULL;
 while(*head != NULL)
 {
 next = (*head)-&gt;next;
 (*head)-&gt;next = new_head;
 new_head = (*head);
 (*head) = next;
 }
 (*head)=new_head;
}
</code></pre>

blocks|key|1397700|text|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;
}

head+=+prev;+//+update+head|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|1397701|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre><code>curr = head;
prev = NULL;

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

head = prev; // update head
</code></pre>

blocks|key|1182309|text|class+Node+{
++++Node+next;
++++int+data;

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

public+class+LinkedList+{

++++static+Node+head;

++++//Print+LinkedList
++++public+static+void+printList(Node+node){

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

++++//Reverse+the+LinkedList+Utility
++++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)+{

++++++++//Creating+LinkedList
++++++++LinkedList.head+=+new+Node(1);
++++++++LinkedList.head.next+=+new+Node(2);
++++++++LinkedList.head.next.next+=+new+Node(3);
++++++++LinkedList.head.next.next.next+=+new+Node(4);

++++++++LinkedList.printList(LinkedList.head);

++++++++Node+node+=+LinkedList.reverse(LinkedList.head);

++++++++LinkedList.printList(node);

++++}


}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|1182310|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre><code>class Node {
 Node next;
 int data;

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

public class LinkedList {

 static Node head;

 //Print LinkedList
 public static void printList(Node node){

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

 //Reverse the LinkedList Utility
 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) {

 //Creating LinkedList
 LinkedList.head = new Node(1);
 LinkedList.head.next = new Node(2);
 LinkedList.head.next.next = new Node(3);
 LinkedList.head.next.next.next = new Node(4);

 LinkedList.printList(LinkedList.head);

 Node node = LinkedList.reverse(LinkedList.head);

 LinkedList.printList(node);

 }


}
</code></pre>

blocks|key|1182356|text|这里有一个更简单的python版本。它只使用了两个指针slow和fast|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1182357|def+reverseList(head:+ListNode)+->+ListNode:

++++slow+=+None
++++fast+=+head
++++while+fast:++
++++++++node_next+=+fast.next
++++++++
++++++++fast.next+=+slow
++++++++slow+=+fast
++++++++++++
++++++++fast+=+node_next
++++return+slow|code-block|syntax|javascript|1182358|entityMap^0|R|4|W|4|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@$9|N|A|O|B|C]|$9|P|A|Q|B|C]]|D|@]|E|$]]|$1|F|3|G|5|H|7|R|8|@]|D|@]|E|$I|J]]|$1|K|3|-4|5|6|7|S|8|@]|D|@]|E|$]]]|L|$]]

Here's a simpler version in python. It does use only two pointers <code>slow</code> &amp; <code>fast</code>
<pre><code>def reverseList(head: ListNode) -&gt; ListNode:

 slow = None
 fast = head
 while fast: 
 node_next = fast.next
 
 fast.next = slow
 slow = fast
 
 fast = node_next
 return slow
</code></pre>

blocks|key|1397831|text|只需使用XOR+linked+list，它在固定时间内是“自然可逆的”，只需交换第一个和最后一个(头部和尾部)指针。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1397832|void+reverse()+noexcept+{+std::swap(first_,+last_);+}|code-block|syntax|javascript|1397833|我已经上传了a+working+example+as+a+project+on+my+GitHub。|1397834|entityMap|0|LINK|mutability|MUTABLE|url|https://en.wikipedia.org/wiki/XOR_linked_list|1|https://github.com/user1095108/xl^0|4|F|0|0|0|6|17|1|0^^$0|@$1|2|3|4|5|6|7|U|8|@]|9|@$A|V|B|W|1|X]]|C|$]]|$1|D|3|E|5|F|7|Y|8|@]|9|@]|C|$G|H]]|$1|I|3|J|5|6|7|Z|8|@]|9|@$A|10|B|11|1|12]]|C|$]]|$1|K|3|-4|5|6|7|13|8|@]|9|@]|C|$]]]|L|$M|$5|N|O|P|C|$Q|R]]|S|$5|N|O|P|C|$Q|T]]]]

Just use an <a href="https://en.wikipedia.org/wiki/XOR_linked_list" rel="nofollow noreferrer">XOR linked list</a>, which is &quot;naturally reversible&quot; in constant time, by just swapping the first and last (head and tail) pointers.
<pre><code>void reverse() noexcept { std::swap(first_, last_); }
</code></pre>
I have uploaded <a href="https://github.com/user1095108/xl" rel="nofollow noreferrer">a working example as a project on my GitHub</a>.

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 <code>p</code>, <code>q</code>, <code>r</code>:

<pre><code>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-&gt;link;
 q-&gt;link = r;
 }
 first = q;
}
</code></pre>

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?

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

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

我想知道是否存在只使用两个指针来反转单链表的逻辑。下面的代码使用三个指针(即p、q、r )来反转单个链表struct node {    int data;    struct node *link;};void reverse() {    struct node *p = first,               ...

问如何仅使用两个指针来反转单链表？
EN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何仅使用两个指针来反转单链表？EN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何仅使用两个指针来反转单链表？
EN