Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1004107
  • 博文数量: 150
  • 博客积分: 3017
  • 博客等级: 少校
  • 技术积分: 3829
  • 用 户 组: 普通用户
  • 注册时间: 2011-11-19 14:40
个人简介

Now in Baidu WISE team

文章分类

全部博文(150)

文章存档

2014年(8)

2013年(31)

2012年(111)

分类: C/C++

2013-01-03 22:01:38

反转一个单链表。
(非递归算法好写,递归算法不是很好写)
合并两个升序有序链表。
codepad.org已验证
 

点击(此处)折叠或打开

  1. #include<stdio.h>
  2. #include<stdlib.h>

  3. typedef struct tagNode{
  4.     int value;
  5.     struct tagNode* next;
  6. }Node;
  7. void outputLinkedList(Node * head){
  8.     while(head!=NULL){
  9.         printf("-->%d ",head->value);
  10.         head = head->next;
  11.     }
  12.     printf("\n");
  13. }
  14. Node * createNode(int value){
  15.     Node * ret = (Node*)malloc(sizeof(Node));
  16.     ret->value = value;
  17.     ret->next = NULL;
  18.     return ret;
  19. }
  20. Node * createLinkedList(){
  21.     Node* ret = NULL;
  22.     int i = 0;
  23.     Node *tmp = NULL;
  24.     for(;i<3;i++){
  25.         ret = createNode(i);
  26.         ret->next = tmp;
  27.         tmp = ret;
  28.     }
  29.     return ret;
  30. }
  31. Node * merge(Node* list1, Node*list2){
  32.     if(list1 == NULL) return list2;
  33.     if(list2 == NULL) return list1;
  34.     Node *ret, *cur;
  35.     if(list1->value <= list2->value){
  36.         cur = list1;
  37.         list1 = list1->next;
  38.     }
  39.     else{
  40.         cur = list2;
  41.         list2 = list2->next;
  42.     }
  43.     ret = cur;
  44.     while((list1!=NULL) && (list2!=NULL)){
  45.         if(list1->value <= list2->value){
  46.             cur->next = list1;
  47.             list1 = list1->next;
  48.         }
  49.         else{
  50.             cur->next = list2;
  51.             list2 = list2->next;
  52.         }
  53.         cur = cur->next;
  54.     }
  55.     if(list1==NULL) cur->next = list2;
  56.     else
  57.         cur->next = list1;
  58.     return ret;
  59. }

  60. Node* revR(Node* head){
  61.     if(head == NULL) return head;
  62.     if(head!=NULL && head->next== NULL)
  63.         return head;

  64.     Node* nxtail = head->next;
  65.     Node* ret = revR(nxtail);
  66.     head->next = NULL;
  67.     nxtail->next = head;
  68.     return ret;
  69. }

  70. Node* revD(Node* head){
  71.     if(head == NULL || head->next == NULL) return head;
  72.     Node *newhead, *tail, *cur;
  73.     tail = NULL;
  74.     cur = head;
  75.     newhead = cur->next;
  76.     do{
  77.         cur->next = tail;
  78.         tail = cur;
  79.         cur = newhead;
  80.         newhead = newhead->next;
  81.     }while(newhead!=NULL);
  82.     cur->next = tail;
  83.     return cur;
  84. }
  85. int main(){
  86.     Node* node = createLinkedList();
  87.     outputLinkedList(node);
  88.     node = revD(node);
  89.     outputLinkedList(node);
  90.     node = revR(node);
  91.     outputLinkedList(node);

  92.     Node* list1 = createLinkedList();
  93.     Node* list2 = createLinkedList();
  94.     node = merge(revD(list1),revR(list2));
  95.     outputLinkedList(node);
  96. }

阅读(1137) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~