C语言数据结构 link 链表反转的实现

C语言数据结构 link 链表反转的实现

链表反转，示例如下：

偶数个输入：a->b->c->d->e->f
偶数个输出：e->f->c->d->a->b
or
奇数个输入：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;
}

如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！