如何仅使用两个指针来反转单向链表?

我会想知道是否存在一些逻辑来扭转链接列表只有两个指针。

以下用于使用三个指针(即p,q,r)来反转单个链表:

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

有没有其他的替代scheme来扭转链表? 就时间复杂性而言,扭转单链表的最佳逻辑是什么?

    任何替代? 不,这个过程很简单,没有根本的不同。 这个algorithm已经是O(n)的时间了,你不能得到比这更快的速度,因为你必须修改每个节点。

    它看起来像你的代码是正确的轨道,但它不是在上面的forms工作。 这是一个工作版本:

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

    我讨厌成为坏消息的持有者,但我不认为你的三指针解决scheme确实有效。 当我在下面的testing工具中使用它时,根据以下输出,列表被简化为一个节点:

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

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

     #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, *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. 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随意使用。

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

    这里是用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 // | | | // vvv // NULL [0]->[1]->[2]->NULL // // Step 2: // // prev head next // | | | // vvv // 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; } 

    是。 我相信你可以用同样的方法做到这一点, 你可以交换两个数字,而不使用第三个数字 。 只需将指针转换为int / long并执行XOR操作几次即可。 这是一个有趣的问题,但没有任何实际价值的C技巧之一。

    你能减lessO(n)的复杂性吗? 不,不是。 只要使用双向链表,如果你认为你需要相反的顺序。

    Robert Sedgewick,“ C中的algorithm ”,Addison-Wesley,1997年第3版,[3.4节]

    如果这不是一个循环列表,那么NULL是最后一个链接。

     typedef struct node* link; 

    typedef struct node* link;

    struct node {
    int item;
    下一步链接;
    };

    / *您将现有列表发送到反向()并返回反向的* /

    链接反向(链接x){
    链接t,y = x,r = NULL;
    while(y!= NULL){
    t = y-> next;
    y-> next = r;
    r = y;
    y = t;
    }
    返回r;
    }

    只是为了好玩(尽pipe尾recursion优化应该停止它吃所有的堆栈):

     Node* reverse (Node *root, Node *end) { Node *next = root->next; root->next = end; return (next ? reverse(next, root) : root); } root = reverse(root, NULL); 

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

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

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

     a = a ^ b ^ (b=a) 

    同样的,

    使用两个交换

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

    解决scheme使用异或

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

    解决scheme在一条线上

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

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

    你需要两个指针:

    第一个指针select第一个节点。 第二个指针select第二个节点。

    处理:

    移动跟踪指针

    将第二个节点指向第一个节点

    先移动第一个指针,将第二个指针指向一个

    将第二个指针移动一步,将Track指针分配给第二个

     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; 

    }

    如何更可读:

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

    这是Java中的一个更简单的版本。 它只使用两个指针currprev

     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 } 

    我不明白为什么有必要回头,因为我们正在通过它作为论据。 我们正在通过链接列表头,然后我们也可以更新。 下面是简单的解决scheme

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

    算出你现在使用的algorithm的时间复杂度,显然它不能被改进。

    不,没有比现在的O(n)更快的事情了。 你需要改变每个节点,所以时间将与元素的数量成正比,这就是你已经拥有的O(n)。

    使用两个指针,同时保持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_reverse()方法,让我知道你们都在想什么。

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

    是的,有一种方法只使用两个指针。 这是通过创build新的链接列表,其中第一个节点是给定列表的第一个节点,第一个列表的第二个节点添加在新列表的开始,等等。

    这是我的版本:

     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来实现这一点,方法是testing驱动开发,因此testing用例也附加。

    代表单个节点的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; } } 

    以启动节点作为input的服务类,并保留它而不使用额外的空间。

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

    以及涵盖以上情况的testing用例。 请注意,你需要junitjar子。 我正在使用testng.jar; 你可以使用任何你喜欢的..

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

    一个简单的algorithm,如果你使用链表作为堆栈结构:

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

    性能可能会受到影响,因为额外的函数调用添加和malloc所以地址交换的algorithm更好,但实际上创build一个新的列表,所以你可以使用其他选项,如sorting或删除项目,如果你添加一个callback函数作为参数相反。

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

    这里有一个简单的解决scheme…

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

    只有一个额外的指针可以解决这个问题,对于反向函数,这个指针必须是静态的。 这是复杂的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; } } 

    作为替代,您可以使用recursion –

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

    使用1个variables的解决scheme(仅限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; 

    你可以去recursion的方法:

    这是伪代码:

     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 ]。 很明显,它只使用了两个指针。