单链表学习

本文发表于KuTear's Blog,转载请注明

创建

定义结构体

typedef struct Node{
  int data;
  struct Node *next;
}node;

创建

node *create(node *header){
 int cycle = 1,input;
 node *p,*s;
 header = (node *)malloc(sizeof(node));
 p = header;
 printf("please input:\n");
 while (cycle) {
     scanf("%d",&input);
     if(input != -1){
         s = (node *)malloc(sizeof(node));
         s->data = input;
         s->next = NULL;
         p->next = s;
         p = s;
     }else{
         cycle = 0;
     }
 }
 //头节点是个空节点,没有数据,把他去掉
 p = header->next;
 free(header);
 return p;
}

长度

int length(node *header){
    int i = 0;
    node *p;
    p = header;
    while (p!=NULL) {
        i++;
        p = p->next;
    }
    return i;
}

排序

冒泡排序,没有修改原始节点的顺序,只是改变他们的值.

node * orderByValue(node *header){
  if(header == NULL || header->next==NULL){
      return header;
  }
  node *p;
  p = header;
  int n = length(header);
  for(int i=0;i<n;i++){
      p = header;
      for(int j = 0;j<n - i -1;j++){
        if(p->data>p->next->data){
            int temp = p->data;
            p->data = p->next->data;
            p->next->data = temp;
        }
        p = p->next;
      }
  }
  return header;
}

反转

node * reversion(node *header){
 node *p,*q,*s;
 p = header;
 s = header;
 //no NODE OR just one NODE
 if(p== NULL || p->next == NULL){
     return header;
 }
 p = header->next;
 s->next = NULL;
 while(p!=NULL){
     q = p->next;
     p->next = s;
     s = p;
     p = q;
 }
 return s;
}

插入

原本链表为小->大的有序链表

node *insert(node *header,int data){
  node *p,*s;
  p = header;
  s = (node *)malloc(sizeof(node));
  s->data = data;
  s->next = NULL;
  if(p == NULL){
    return s;
  }
  if(p->data > data){
      s->next = p;
      return s;
  }
  while(p->next!=NULL){
   if(p->data <= data && p->next->data>data){
      s->next = p->next;
      p->next = s;
      return header;
   }
   p = p->next;
  }
  if(p->next == NULL){
      p->next = s;
      return header;
  }

}

打印

void print(node *header){
 node *p;
 p = header;
 printf("Current Node: ");
 while(p!=NULL){
  printf("%d  ",p->data);
  p = p->next;
 }
 printf("\n");
}

删除

node *deleteNodeWithData(node *header,int data){
  node *p,*s;
  p = header;
  if(header == NULL){
      return NULL;
  }
  while(p->data!=data && p->next!=NULL){
    s = p;
    p = p->next;
  }
  if(p->data == data){
    if(p == header){
        header = header->next;
        free(p);
    }else{
        s->next = p->next;
        free(p);
    }
  }else{
    printf("Node not exist! \n");
  }
  return header;
}

测试

int main(void){
  node * header = NULL;
  header = create(header);
  print(header);
  printf("Length:%d \n",length(header));
  int deleteNode;
  printf("Delete:");
  scanf("%d",&deleteNode);
  header = deleteNodeWithData(header,deleteNode);
  print(header);
  printf("After Order:");
  header = orderByValue(header);
  print(header);
  int insertData;
  printf("Insert:");
  scanf("%d",&insertData);
  header = insert(header,insertData);
  print(header);
  header = reversion(header);
  printf("after :");
  print(header);
  return 0;
}

运行结果

面试题

1. 求单链表中结点的个数
2. 将单链表反转
3. 查找单链表中的倒数第K个结点（k > 0)(参考)
4. 查找单链表的中间结点(参考)
5. 从尾到头打印单链表
6. 已知两个单链表pHead1 和pHead2 各自有序，把它们合并成一个链表依然有序
7. 判断一个单链表中是否有环(注重理解)
8. 判断两个单链表是否相交(尾节点相同)
9. 在可能有环的情况下上题又会怎样
10. 求两个单链表相交的第一个节点
11. 已知一个单链表中存在环，求进入环中的第一个节点
12. 给出一单链表头指针pHead和一节点指针pToBeDeleted，O(1)时间复杂度删除节点pToBeDeleted

答案与解析