首页 > 代码库 > 链表逆序输出 ---九度1511

链表逆序输出 ---九度1511

2024-07-10 21:45:39   226人阅读

题目描述：

输入一个链表，从尾到头打印链表每个节点的值。

 

输入：

每个输入文件仅包含一组测试样例。
每一组测试案例包含多行，每行一个大于0的整数，代表一个链表的节点。第一行是链表第一个节点的值，依次类推。当输入到-1时代表链表输入完毕。-1本身不属于链表。

 

输出：

对应每个测试案例，以从尾到头的顺序输出链表每个节点的值，每个值占一行。

 

样例输入：
12345-1
样例输出：
54321
解题思路：
方法一：直接用数组存储数据，然后反向输出，不过好像通不过。为什么？
方法二：利用单向链表存储数据，在输出的时候递归输出，先输出根节点的下一个节点，再输出当前节点，类似于树的后序遍历。这种方法由于需要递归调用，运行过程中占用的空间会更大。
方法三：使用双向链表，在输出的时候可以直接从链表的尾部从后向前输出。
以上两种方法，如果采用正常的创建链表和输出链表的方法，会导致运行时间过长。此时，用到的小技巧是，每次传入到链表中的不是根节点的地址，而是链表尾部的非空节点的地址，这样插入的时间复杂度就是O(1)了，不需要每次多从头到尾查找插入位置。输出的时间复杂度就是O(n)。这样，两种方法都能通过，但是方法三所用的空间更少一些。

  1 #include<stdio.h>  2 #include<stdlib.h>  3 #include<string.h>  4 #define N 100  5    6 void printArrayList();  7    8 /*单向链表节点*/  9 struct Node{ 10     int value; 11     Node* next; 12 }; 13   14 /*双向链表节点*/ 15 struct BiNode{ 16     int value; 17     BiNode* next; 18     BiNode* previous; 19 }; 20   21 /* 逆序输出双向链表 */ 22 void rPrintBiList(BiNode* root){ 23     if(root == NULL){ 24         return; 25     } 26     BiNode* tmp; 27     BiNode* parent; 28     tmp = root; 29     parent = root; 30     while(tmp!=NULL){ 31         parent = tmp; 32         tmp = tmp ->next; 33     } 34       35     while(parent !=NULL){ 36         printf("%d\n",parent->value); 37         parent = parent ->previous; 38     } 39 } 40   41   42 /* 逆序输出链表 */ 43 void rPrintList(Node* root){ 44     if(root ==NULL){ 45         return; 46     } 47     rPrintList(root->next); 48     printf("%d\n",root->value); 49 } 50   51 void rPrintListTail(BiNode* tail){ 52     if( tail == NULL){ 53         return ; 54     } 55     while(tail != NULL){ 56         printf("%d\n",tail->value); 57         tail = tail->previous; 58     } 59 } 60   61   62 /* 将数据插入到双向链表的尾部 */ 63 void addToBiList(BiNode** root,int value){ 64     /* 对每一个输入点建立一个链表 */ 65     BiNode* proot = new BiNode(); 66     proot -> value =http://www.mamicode.com/ value; 67     proot -> next = NULL; 68     BiNode* tmp; 69     BiNode* parent; 70     if(*root ==NULL){ 71         *root = proot; 72         proot ->previous = NULL; 73     }else{ 74         tmp = *root; 75         parent = *root; 76         while(tmp !=NULL){ 77             parent = tmp; 78             tmp = tmp ->next; 79         }       80         parent ->next= proot; 81         proot ->previous = parent; 82     } 83 } 84   85 /* 直接插入链表的尾部 */ 86 void addToBiListTail(BiNode** tail,int value){ 87     BiNode* proot = new BiNode(); 88     proot -> value =http://www.mamicode.com/ value; 89     proot -> next = NULL; 90     if(*tail==NULL){ 91         *tail = proot; 92         proot ->previous = NULL; 93     }else{ 94         (*tail)->next= proot; 95         proot ->previous= *tail; 96         *tail = proot; 97     } 98 } 99  100  101 void addToListTail(Node** tail,int value){ // 此时必须使用Node** 作为参数，因为我们不仅需要tail所只想的内容发生改变，它自身的值也发生改变，所以需要使用指针的指针作为参数。！！！102     /* 对每一个输入点建立一个链表 */103     Node* proot = new Node();104     proot -> value =http://www.mamicode.com/ value;105     proot -> next = NULL;106     if(*tail==NULL){107         *tail = proot;108     }else{109         (*tail) ->next= proot;110         *tail = proot;111     }112 }113 /* 把数据插入到链表的尾部 */114 void addToList(Node** root,int value){115      116     /* 对每一个输入点建立一个链表 */117     Node* proot = new Node();118     proot -> value =http://www.mamicode.com/ value;119     proot -> next = NULL;120     Node* tmp;121     Node* parent;122  123     /* 将新的节点插入到链表中去*/124     if(*root == NULL){125         *root = proot; 126     }else{127         tmp = *root;128         parent = *root; //最后一个不为NULL的节点129         while(tmp!=NULL){130             parent = tmp;131             tmp = tmp->next;132         }133         parent->next = proot;134     }135      136 }137  138 /*   使用数组来存放数据 */139 void printArrayList(){140     int* intArray = (int *)malloc(sizeof(int)*N);141     int* tmp;142     int len = N;143     int input;144     int count=0;145     scanf("%d",&input);146     while(input!=(-1)){147         if(input<0){148             break;149         }150         if(count == len){151             len += N;152             tmp = (int *)realloc(intArray,len);153             intArray = tmp;154         }155         intArray[count++] = input;156         scanf("%d",&input);157     }158     for(int i = count-1; i>=0 ; i--){159         printf("%d\n",intArray[i]);160     }161 }162  163 int main(){164  165     /*printArrayList();*/166     int n;167     Node* root=NULL;168     Node* nodetail=NULL;169     BiNode* biroot = NULL;170     BiNode* tail = NULL;171     bool isFirst = true;172     scanf("%d",&n);173     while(n!=(-1)){174         /*addToList(&root,n);*/175         addToListTail(&nodetail,n);176         if(isFirst){177             root = &(*nodetail);178             isFirst = false;179         }180     /*  addToBiList(&biroot,n);*/181     /*  addToBiListTail(&tail,n);*/182         scanf("%d",&n);183     }184     /*rPrintList(root);*/185     rPrintList(root);186     /*rPrintBiList(biroot);*/187     /*rPrintListTail(tail);*/188     return 0;189 }190  191  192  193 /**************************************************************194     Problem: 1511195     User: jingxmu196     Language: C++197     Result: Accepted198     Time:90 ms199     Memory:5544 kb200 ****************************************************************/
 






























        

            
                
                  
                
                

                    联系

                    我们