C语言数据结构 link 链表反转的实现
链表反转，示例如下：
偶数个输入：a->b->c->d->e->f偶数个输出：e->f->c->d->a->bor奇数个输入：a->b->c->d->e->f->g偶数个输出：g->e->f->c->d->a->b
#include <stdio.h> #include <malloc.h> #include <stdlib.h> /************** start of stack *************/ #define STACK_SIZE 1024 char stack[STACK_SIZE]; int top = 0; void push(char ch){ stack[top] = ch; top++; } char pop(){ top--; return stack[top]; } int isempty(){ return 0 == top; } void test_stack(){ push('a'); push('b'); push('c'); push('d'); while(!isempty()){ printf("pop ch: %c\n", pop()); } } /************** end of stack *************/ struct _node{ char data; struct _node *next; }; typedef struct _node node, *plink; plink init_link(){ plink pl; pl = (plink)malloc(sizeof(node)); // check malloc success or not if(NULL == pl) { printf("malloc memory fail..."); return NULL; } // init link head pl->data = '\0'; pl->next = NULL; return pl; } void input_data(plink pl, char data){ plink p = pl; while(p->next){ p = p->next; } plink node = NULL; node = (plink)malloc(sizeof(node)); // malloc a new node // add data if(NULL != node){ node->data = data; node->next = p->next; // last next is NULL p->next = node; p = node; // p point last node } } void output_link(plink pl){ if(NULL == pl){ printf("plink is null"); return; } plink p = pl->next; // already check pl is NULL, so here is ok while(NULL != p){ printf("%c -> ", p->data); p = p->next; } printf("\n\n"); } // push and pop stack plink revert_link2(plink pl){ plink p = pl; while(p->next){ // printf("p->data: %c\n", p->next->data); if(p->next->next){ push(p->next->next->data); push(p->next->data); p = p->next->next; } else { push(p->next->data); p = p->next; } } while(!isempty()){ printf("%c -> ", pop()); } printf("\n\n"); return NULL; } plink revert_link(plink pl){ if(NULL == pl){ // check link is NULL return NULL; } int link_len = 0; plink tmp_pl = pl->next; while(tmp_pl){ // count link count link_len++; tmp_pl = tmp_pl->next; } // link length is no more than two node(s) if(link_len <= 2){ return pl; } // link length is more than two nodes return revert_link2(pl); } int main(){ plink pl = NULL; pl = init_link(); // init link head input_data(pl, 'a'); // add data input_data(pl, 'b'); input_data(pl, 'c'); input_data(pl, 'd'); input_data(pl, 'e'); input_data(pl, 'f'); input_data(pl, 'g'); output_link(pl); plink pl2 = revert_link(pl); output_link(pl2); return 0; } /**** revert_link.c linux gcc compile gcc revert_link.c -o revert_link && ./revert_link output result: a -> b -> c -> d -> e -> f -> g g -> e -> f -> c -> d -> a -> b or a -> b -> c -> d -> e -> f e -> f -> c -> d -> a -> b ****/
间隔螺旋反转：
输入： a -> b -> c -> d -> e -> f 输出： b -> a -> d -> c -> f -> e
plink revert_link3(plink pl){ if(NULL == pl){ printf("plink is null"); return NULL; } plink p = pl; plink first = p->next; while(NULL != first){ plink second = first->next; if(NULL != second){ first->next = second->next; // third node second->next = first; // revert two nodes first = first->next; p->next = second; p = second->next; } } return pl; }
如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
每一件事都要用多方面的角度来看它
