单链表反转算法（递归/非递归）/合并两个升序链表

反转一个单链表。

（非递归算法好写，递归算法不是很好写）

合并两个升序有序链表。

codepad.org已验证

 

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

typedef struct tagNode{
    int value;
    struct tagNode* next;
}Node;
void outputLinkedList(Node * head){
    while(head!=NULL){
        printf("-->%d ",head->value);
        head = head->next;
    }
    printf("\n");
}
Node * createNode(int value){
    Node * ret = (Node*)malloc(sizeof(Node));
    ret->value = value;
    ret->next = NULL;
    return ret;
}
Node * createLinkedList(){
    Node* ret = NULL;
    int i = 0;
    Node *tmp = NULL;
    for(;i<3;i++){
        ret = createNode(i);
        ret->next = tmp;
        tmp = ret;
    }
    return ret;
}
Node * merge(Node* list1, Node*list2){
    if(list1 == NULL) return list2;
    if(list2 == NULL) return list1;
    Node *ret, *cur;
    if(list1->value <= list2->value){
        cur = list1;
        list1 = list1->next;
    }
    else{
        cur = list2;
        list2 = list2->next;
    }
    ret = cur;
    while((list1!=NULL) && (list2!=NULL)){
        if(list1->value <= list2->value){
            cur->next = list1;
            list1 = list1->next;
        }
        else{
            cur->next = list2;
            list2 = list2->next;
        }
        cur = cur->next;
    }
    if(list1==NULL) cur->next = list2;
    else
        cur->next = list1;
    return ret;
}

Node* revR(Node* head){
    if(head == NULL) return head;
    if(head!=NULL && head->next== NULL)
        return head;

    Node* nxtail = head->next;
    Node* ret = revR(nxtail);
    head->next = NULL;
    nxtail->next = head;
    return ret;
}

Node* revD(Node* head){
    if(head == NULL || head->next == NULL) return head;
    Node *newhead, *tail, *cur;
    tail = NULL;
    cur = head;
    newhead = cur->next;
    do{
        cur->next = tail;
        tail = cur;
        cur = newhead;
        newhead = newhead->next;
    }while(newhead!=NULL);
    cur->next = tail;
    return cur;
}
int main(){
    Node* node = createLinkedList();
    outputLinkedList(node);
    node = revD(node);
    outputLinkedList(node);
    node = revR(node);
    outputLinkedList(node);

    Node* list1 = createLinkedList();
    Node* list2 = createLinkedList();
    node = merge(revD(list1),revR(list2));
    outputLinkedList(node);
}