如何只使用两个指针来反转单链表？

我想知道是否存在仅使用两个指针来逆转单链表的逻辑。

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

是否有其他替代方法来反转链表？就时间复杂性而言，逆转单链表的最佳逻辑是什么？

266755 次浏览
小开

Yes. I'm sure you can do this the same way 你可以不用第三个号码交换两个号码. 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.

你能降低 O (n)的复杂度吗？不，没有。如果你认为你需要相反的顺序，那就用双向链表。

小开

计算出你现在使用的算法的时间复杂度，很明显，它不能被改进。

小开
最佳答案

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.

看起来您的代码正处于正确的轨道上，但是在上面的表单中并不能很好地工作。下面是一个可行的版本:

#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;
}
小开

我不想告诉你坏消息，但我不认为你的三分球解决方案真的有效。当我在下面的测试工具中使用它时，列表缩减为一个节点，如下面的输出所示:

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

你不会得到比你的解决方案更好的时间复杂性，因为它是 O (n) ，你必须访问每个节点来改变指针，但是你 can做一个解决方案只有两个额外的指针很容易，如下面的代码所示:

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

此代码输出:

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

我想这就是你想要的。它实际上可以这样做，因为一旦将 first加载到遍历列表的指针中，就可以随意重用 first。

小开

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.

小开

只是为了好玩(尽管尾递归优化应该可以阻止它吞噬所有堆栈) :


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


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


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


root = reverse(root, NULL);
小开

可读性更强的怎么样:


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

解决方案使用1个变量(只有 P) :

typedef unsigned long AddressType;


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


/* Reversing linked list */
p = first;


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


first = p;
小开 
#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;
}
小开

罗伯特·塞奇威克，“ abc 0”，艾迪生-韦斯利，第3版，1997年，[第3.4节]

如果这不是循环列表，则 NULL 是最后一个链接。 

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

小开

只需要一个额外的指针就可以解决这个问题，这个指针对于反向函数必须是静态的。它是 O (n)复杂度。

#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;
}
}
小开

使用两个指针，同时保持 O (n)的时间复杂性(最快可达到的) ，可能只能通过对指针进行数字强制转换并交换它们的值来实现。下面是一个实现方案:

#include <stdio.h>


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


void reverse(node* head)
{
node* ptr;
if(!head || !head->next || !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 ^ (unsigned)(head->next =\
(unsigned)head->next ^ (unsigned)ptr)) ^ (unsigned)head->next;


/* Swap head->next->next and ptr. */
head->next->next = (unsigned)(ptr =\
(unsigned)ptr ^ (unsigned)(head->next->next =\
(unsigned)head->next->next ^ (unsigned)ptr)) ^ (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("%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;
node* dummy_head;
dummy_head->next = NULL;
for(i = 1; i <= n ; ++i) add_end(dummy_head, i);
print(dummy_head);
reverse(dummy_head);
print(dummy_head);
erase(dummy_head);
}
小开

我有一个稍微不同的方法。我想利用现有的函数(如 insert _ at (index)、 delete _ from (index))来反转列表(类似于右移操作)。复杂度仍然是 O (n) ，但优点是更多的重用代码。看看 another _ return ()方法，让我知道你们的想法。

#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%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;


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


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


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


// 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;
}
小开 
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 ....


}


}
小开 
#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;
}
小开

你可以采用递归的方法:

下面是伪代码:

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

在对函数进行调用之后，它返回链表的新根[ temp]。 因为很明显它只使用了两个指针。

小开 
//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...
小开 
#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("%d",&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("%d%d",&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++;
}
if(pre==NULL)
{
printf("Invalid position");
}
else
{
cur->link=pre->link;
pre->link=cur;
}
}
}
void display()
{
cur=first;
while(cur!=NULL)
{
printf("data= %d\t address= %u\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("%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);
}
小开

要在不使用临时变量的情况下交换两个变量,

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

最快的方法是把它写成一行

a = a ^ b ^ (b=a)

同样地,

用两次掉期

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

使用 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)

相同的逻辑用于反向链表。

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 ^ (int)q ^ (int)q->next ^ (int)(q->next=p) ^ (int)(p=q));
}
head = p;
return head;
}
小开

这是 reverse a singly linked list in C的密码。

这里贴的是:

// 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;
}
小开

这里有个简单的解决办法。

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

是的，有一种方法只使用两个指针。即通过创建新的链表，其中第一个节点是给定列表的第一个节点，第一个列表的第二个节点添加到新列表的开始处，依此类推。

小开

Here is my version:

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

哪里

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

我使用 java 来实现这个，方法是测试驱动的开发，因此测试用例也是附加的。

表示单个节点的 Node 类-

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

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

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




}

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..

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




}
}
小开

作为替代方法，您可以使用递归-

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

你需要一个 轨迹指针来跟踪列表。

你需要两点建议:

第一个指针 选择第一个节点。 第二个指针 选择第二个节点。

处理:

移动轨迹指针

点第二个节点到第一个节点

将第一个指针移动一步，方法是将第二个指针分配给第一个指针

将第二个指针移动一步，方法是将跟踪指针分配给第二个

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;

}

小开

如果使用链表作为堆栈结构，这是一个简单的算法:

 #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++ < 26 ) add(&head, i, i+'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("%d:%c\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;


}

性能可能会受到影响，因为额外的函数调用 add 和 malloc，所以地址交换的算法是更好的，但实际上一个创建新的列表，所以你可以使用额外的选项，如排序或删除项，如果你添加一个回调函数作为参数的反向。

小开

下面是 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;
}

输出 给你

小开

下面是一个使用2个指针(head 和 r)的实现

ListNode * reverse(ListNode* head) {


ListNode *r = NULL;


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


while(r) {
head = reinterpret_cast<ListNode*>(size_t(head) ^ size_t(r->next));
r->next = reinterpret_cast<ListNode*>(size_t(r->next) ^ size_t(head));
head = reinterpret_cast<ListNode*>(size_t(head) ^ size_t(r->next));


head = reinterpret_cast<ListNode*>(size_t(head) ^ size_t(r));
r = reinterpret_cast<ListNode*>(size_t(r) ^ size_t(head));
head = reinterpret_cast<ListNode*>(size_t(head) ^ size_t(r));
}
return head;
}
小开

下面是 Java 中的一个简单版本，它只使用了两个指针 curr和 prev

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
}
小开

我不明白为什么有必要回头，因为我们传递它作为论点。我们正在传递链接列表的头，然后我们可以更新也。下面是一个简单的解决方案。

#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++)
printf (" %d ==> %d \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;
}
小开 
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
小开 
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);


}




}
小开

只需使用一个额外指针就可以简单地逆转链表。 这样做的关键是使用递归。

这是用 Java 编写的程序。

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


public Node reverseLinkedListRecursion(Node p) {
if (p.next == null) {
head = p;
q = p;
return q;
} else {
reverseLinkedListRecursion(p.next);
p.next = null;
q.next = p;
q = p;
return head;
}
}


// call this function from your main method.
reverseLinkedListRecursion(head);

正如您所看到的，这是一个头递归的简单示例。 我们主要有两种不同的递归。

  1. Head Recursion:- When the Recursion is the first thing executed by a function.
  2. 尾递归:-当递归是函数执行的最后一个操作时。

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

在这里，堆栈帧将不断返回，直到堆栈为空。

小开

这是一个简单的 python 版本，它只使用两个指针 slow和 fast

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
小开

只要使用 异或链表，这是“自然可逆”在恒定的时间，只需交换第一个和最后(头和尾)指针。

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

我上传了 作为我的 GitHub 项目的一个工作示例。


提交答案