如果给定一个链表,不能改变数据,也就是不能通过反转链表来实现,将链表从后往前打印出来。怎么实现呢?用一个辅助栈,每访问到一个节点的时候,将节点的数据存到栈中,访问完所有的节点之后,将栈中的元素从栈顶打印到栈底。核心代码如下:
//把节点加到链表中,每次在pHead后面加节点 void Add(NODE *pHead, int v) { node[++top].data = v; node[top].next = pHead->next; pHead->next = &node[top]; } //从头到尾打印节点 void ReversePrintLink(NODE *pHead) { top = -1; NODE *p = pHead->next; while(p != NULL) { stack[++top] = p->data; p = p->next; } while(top) printf("%d ", stack[top--]); if(top == 0) printf("%d\n",stack[0]); }
题目扩展:
1、用链表模拟约瑟夫环
//节点出链表 void Delete(NODE *pPreDele) {//这里内存一次性申请的,所以不需要释放内存 pPreDele->next = pPreDele->next->next; } int Joseph(NODE *pHead, int k) { NODE *p = pHead->next; if(!p)//一个元素也没有 return -1; int cnt = 0; while(p->next != p) { ++cnt; if(cnt == k - 1) { Delete(p); cnt = 0; } p = p->next; } return p->data; }
2、复杂链表的复制(这个过段时间再补充)
另:下面给出数据结构、变量的定义及main函数的调用:
#include<stdio.h> struct NODE { int data; NODE *next; }; const int N = 30; NODE node[N]; int stack[N]; int top; int main() { int n,i,v; NODE Head; /*while(scanf("%d", &n) != EOF) { top = -1; Head.next = NULL; for(i = 0; i < n; ++i) { scanf("%d",&v); Add(&Head, v); } ReversePrintLink(&Head); }*/ while(scanf("%d %d", &n, &k) != EOF) { top = -1; Head.next = NULL; for(i = 1; i <= n; ++i) { Add(&Head, i); } if(n > 0)//node[0]是第一个加入的元素,也在链表尾部 node[0].next = Head.next; printf("%d\n", Joseph(&Head, k)); } }