Как отменить односвязный список, используя только два указателя?

Мне было бы интересно, существует ли какая-то логика для изменения связанного списка, используя только два указателя.

Для разворота одиночного связанного списка используется три указателя, а именно 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; } 

Есть ли другой альтернативный вариант для изменения связанного списка? какова была бы лучшая логика для обращения к односвязному списку с точки зрения временной сложности?

Любая альтернатива? Нет, это так же просто, как и получается, и нет принципиально другого способа сделать это. Этот алгоритм уже O (n) времени, и вы не можете получить быстрее, чем это, так как вы должны изменить каждый узел.

Похоже, что ваш код находится на правильном пути, но он не работает в приведенной выше форме. Вот рабочая версия:

 #include  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), и вам нужно посетить каждый узел, чтобы изменить указатели, но вы можете легко сделать решение только с двумя дополнительными указателями, как показано в следующем коде:

 #include  // 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 указатель, перемещающийся по списку, вы можете повторно использовать его по своему усмотрению.

 #include  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  #include  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 пару раз. Это один из тех трюков, которые делают интересный вопрос, но не имеют практической ценности.

Можете ли вы уменьшить сложность O (n)? Нет, не совсем. Просто используйте двойной список, если вы считаете, что вам понадобится обратный порядок.

Роберт Седжвик, « Алгоритмы в С », Эддисон-Уэсли, 3-е издание, 1997, [Раздел 3.4]

В случае, если это не циклический список, значит, NULL является последней ссылкой.

 typedef struct node* link; 

typedef struct node* link;

struct node {
int item;
link next;
};

/ * вы отправляете существующий список на reverse () и возвращает обратный один * /

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

Просто для удовольствия (хотя оптимизация хвостовой рекурсии должна прекратить ее есть весь стек):

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

Чтобы заменить две переменные без использования временной переменной,

 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 

решение в одной строке

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

Вам нужен указатель дорожки, который будет отслеживать список.

Вам нужны два указателя:

первый указатель на выбор первого узла. второй указатель для выбора второго узла.

Обработка:

Переместить указатель пути

Перенесите второй узел на первый узел

Перенесите первый указатель на один шаг, назначив второй указатель на один

Переместить второй указатель на один шаг, назначив указатель дорожки второму

 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* 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. Он использует только два указателя 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 #include 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  #include  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; } 

Разработайте временную сложность алгоритма, который вы используете сейчас, и должно быть очевидно, что его нельзя улучшить.

Нет, ничего не может быть сделано быстрее, чем текущий O (n). Вам нужно изменить каждый узел, поэтому время будет пропорционально количеству элементов, и у вас уже есть O (n).

Используя два указателя, сохраняя при этом временную сложность O (n), наиболее быстрая достижимость может быть возможна только путем литья указателей и замены их значений. Вот реализация:

 #include  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); } в #include  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); } в #include  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  #include  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 .... } } в 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 .... } } в 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 .... } } о 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 #include #include 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(clink; 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); } в #include #include #include 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(clink; 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); } В #include #include #include 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(clink; 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); } в #include #include #include 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(clink; 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); } в #include #include #include 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(clink; 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); } в #include #include #include 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(clink; 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); } 

Да, есть способ использовать только два указателя. То есть путем создания нового связанного списка, где первый узел является первым узлом данного списка, а второй узел первого списка добавляется в начале нового списка и так далее.

Вот моя версия:

 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 : [email protected] * 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; } } 

Класс обслуживания, который принимает начальный узел в качестве входных данных и резервирует его, не используя дополнительное пространство.

 package com.adnan.linkedlist; /** * User : Adnan * Email : [email protected] * 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; } } 

И тестовый сценарий, который охватывает сценарий выше. Обратите внимание, что вам нужны банки junit. Я использую testng.jar; вы можете использовать любое, что угодно вам.

 package com.adnan.linkedlist; import org.testng.annotations.Test; import static org.testng.AssertJUnit.assertTrue; /** * User : Adnan * Email : [email protected] * 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(); } } } 

Простой алгоритм, если вы используете связанный список как структуру стека:

  #include  #include  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  struct Node{ Node(): next(NULL){} Node *next; std::string data; }; void printlist(Node* l){ while(l){ std::cout<data<next; } std::cout<<"----"<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; } в #include  struct Node{ Node(): next(NULL){} Node *next; std::string data; }; void printlist(Node* l){ while(l){ std::cout<data<next; } std::cout<<"----"<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; } в #include  struct Node{ Node(): next(NULL){} Node *next; std::string data; }; void printlist(Node* l){ while(l){ std::cout<data<next; } std::cout<<"----"<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(size_t(head) ^ size_t(r->next)); r->next = reinterpret_cast(size_t(r->next) ^ size_t(head)); head = reinterpret_cast(size_t(head) ^ size_t(r->next)); head = reinterpret_cast(size_t(head) ^ size_t(r)); r = reinterpret_cast(size_t(r) ^ size_t(head)); head = reinterpret_cast(size_t(head) ^ size_t(r)); } return head; } 

вот немного простого решения …

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

В качестве альтернативы вы можете использовать рекурсию,

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

Решение с использованием 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; 
Давайте будем гением компьютера.