كيفية عكس قائمة مرتبطة منفردة باستخدام مؤشرين فقط؟
https://stackoverflow.com/questions/1801549
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
سأتساءل عما إذا كان هناك بعض المنطق لعكس القائمة المرتبطة باستخدام مؤشرين فقط.
يتم استخدام ما يلي لعكس القائمة المرتبطة الفردية باستخدام ثلاثة مؤشرات وهي 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;
}
هل هناك أي بديل آخر لعكس القائمة المرتبطة؟ما هو المنطق الأفضل لعكس قائمة مرتبطة بشكل فردي، من حيث التعقيد الزمني؟
المحلول
وأي بديل؟ لا، هذا هو بسيط كما يحصل، وليس هناك طريقة جوهريا-مختلفة للقيام بذلك. هذه الخوارزمية هي بالفعل O (ن) وقت، وأنت لا تستطيع الحصول على أي أسرع من ذلك، كما يجب تعديل كل عقدة.
ويبدو مثل الرمز الخاص بك هو على الطريق الصحيح، ولكنه لا يعمل تماما في شكل أعلاه. وفيما يلي نسخة العمل:
#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 (ن) وكان لديك لزيارة كل عقدة لتغيير مؤشرات، لكنك <م> يمكن القيام حل مع اثنين فقط مؤشرات إضافية بسهولة تامة، كما هو موضح في التعليمات البرمجية التالية:
#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
// | | |
// 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;
}
نعم. أنا متأكد من أنك يمكن أن تفعل هذا نفس الطريقة لك يمكن مبادلة رقمين دون استخدام الثالث. ببساطة يلقي مؤشرات لكثافة العمليات / طويل وتنفيذ العملية XOR بضع مرات. هذا هو واحد من تلك الحيل C الذي يجعل لسؤال متعة، ولكن ليس لديها أي قيمة عملية.
ويمكنك تقليل O (ن) التعقيد؟ لا ليس بالفعل كذلك. مجرد استخدام قائمة مرتبطة مضاعف إذا كنت تعتقد انك تسير في حاجة إلى ترتيب عكسي.
روبرت سيدجويك"الخوارزميات في C"، أديسون ويسلي، الطبعة الثالثة، 1997، [القسم 3.4]
في حالة عدم وجود قائمة دورية، فإن NULL هو الرابط الأخير.
typedef struct node* link;
struct node {int item ؛الرابط التالي؛};
/* تقوم بإرسال القائمة الموجودة إلى الاتجاه العكسي () وإرجاع القائمة المعكوسة */
Link Reverse (Link X) {link t ، y = x ، r = null ؛بينما (y! = null) {t = y-> التالي ؛y-> next = r;ص = ص؛ص = ر؛} 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;
}
أنت بحاجة إلى مؤشر المسار والتي سوف تتبع القائمة.
تحتاج إلى مؤشرين:
المؤشر الأول لاختيار العقدة الأولى. المؤشر الثاني لاختيار العقدة الثانية.
يعالج :
تحريك مؤشر التتبع
أشر العقدة الثانية إلى العقدة الأولى
حرك المؤشر الأول خطوة واحدة، عن طريق تعيين المؤشر الثاني إلى واحد
حرك المؤشر الثاني خطوة واحدة، عن طريق تعيين مؤشر المسار إلى الثانية
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);
}
وهنا صيغة أبسط في جاوة. أنها لا تستخدم سوى اثنين من المؤشرات 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;
}
#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;
}
والعمل على تعقيد الوقت خوارزمية الذي تستخدمه الآن، وينبغي أن يكون واضحا أنه لا يمكن تحسينها.
لا، (ن) لا يمكن فعل شيء أسرع من O الحالي. تحتاج إلى تغيير كل عقدة، لذلك الوقت سيكون متناسبا مع عدد من العناصر على أي حال، وهذا هو O (ن) كان لديك بالفعل.
وباستخدام اثنين من المؤشرات مع الحفاظ على تعقيد وقت O (ن)، أسرع تحقيقه، قد يكون ممكنا إلا من خلال عدد من المؤشرات الصب ومبادلة قيمهم. هنا هو التنفيذ:
#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 (رقم قياسي)، delete_from (فهرس)) لعكس القائمة (ما يشبه عملية التحول اليمنى). تعقيد لا يزال O (ن) ولكن ميزة هي رمز أكثر إعادة استخدامها. إلقاء نظرة على 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);
}
ونعم هناك طريقة باستخدام اثنين فقط مؤشرات. وهذا هو طريق إنشاء قائمة جديدة مرتبطة حيث العقدة الأولى يتم إضافة العقدة الأولى من قائمة معينة، والعقدة الثانية من القائمة الأولى في بداية القائمة الجديدة وهلم جرا.
وهنا هو الإصدار الخاص بي:
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;
};
وأنا باستخدام جافا لتنفيذ هذا النهج والتنمية اختبار يحركها بالتالي هي التي تعلق أيضا حالات الاختبار.
والطبقة عقدة التي تمثل عقدة واحدة -
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;
}
}
والطبقة الخدمة التي تأخذ بدء عقدة كمدخل وحجز بدون استخدام مساحة إضافية.
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;
}
}
وقضية الاختبار التي تغطي أعلى السيناريو. الرجاء ملاحظة أنك بحاجة الجرار أداة JUnit. أنا أستخدم 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();
}
}
}
وخوارزمية بسيطة إذا كنت تستخدم القائمة المرتبطة كهيكل كومة:
#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 ذلك خوارزميات مقايضة عنوان أفضل ولكن هذا واحد يخلق في الواقع قائمة جديدة حتى تتمكن من استخدام خيارات إضافية مثل نوع أو إزالة عناصر إذا قمت بإضافة دالة رد كما معلمة إلى الاتجاه المعاكس.
وهنا نهجا مختلفا قليلا، ولكن بسيط في 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 المؤشرات (رئيس وص)
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;
}
وهنا هو القليل من حل بسيط ...
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 (ن) التعقيد.
#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;
}
}
وكبديل، يمكنك استخدام العودية -
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
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);
}
}
لا تنتمي إلى StackOverflow
