1 #include<iostream>

  2

  3 struct Node

  4 {

  5     int data;

  6     Node *next;

  7 };

  8

  9 typedef struct Node Node;

 10

 11 Node *Reverse(Node *head)

 12 {

 13     if (NULL == head || NULL == head->next)

 14         return head;

 15     Node *p1 = head;

 16     Node *p2 = p1->next;

 17     Node *p3 = p2->next;

 18     p1->next = NULL;

 19     while (p3 != NULL)

 20     {

 21         p2->next = p1;

 22         p1 = p2;

 23         p2 = p3;

 24         p3 = p3->next;

 25     }

 26

 27     p2->next = p1;

 28     head = p2;

 29     return head;

 30 }

 31

 32 // 循环算法

 33 Node *Merge(Node *head1, Node *head2)

 34 {

 35     if (NULL == head1)

 36         return head2;

 37     if (NULL == head2)

 38         return head1;

 39     Node *head = NULL;

 40     Node *p1 = NULL;

 41     Node *p2 = NULL;

 42     if (head1->data < head2->data)

 43     {

 44         head = head1;

 45         p1 = head1->next;

 46         p2 = head2;

 47     }

 48     else

 49     {

 50         head = head2;

 51         p2 = head2->next;

 52         p2 = head1;

 53     }

 54

 55     Node *cur = head;

 56     while (NULL!=p1 && NULL!=p2)

 57     {

 58         if (p1->data < p2->data)

 59         {

 60             cur->next = p1;

 61             cur = p1;

 62             p1 = p1->next;

 63         }

 64         else

 65         {

 66             cur->next = p2;

 67             cur = p2;

 68             p2 = p2->next;

 69         }

 70     }

 71     if (NULL == p1)

 72         cur->next = p2;

 73     if (NULL == p2)

 74         cur->next = p1;

 75

 76     return head;

 77 }

 78

 79 // 递归算法

 80 Node *MergeRecursive(Node *head1, Node *head2)

 81 {

 82     if (NULL == head1)

 83         return head2;

 84     if (NULL == head2)

 85         return head1;

 86     Node *head = NULL;

 87

 88     if (head1->data < head2->data)

 89     {

 90         head = head1;

 91         head->next = MergeRecursive(head1->next, head2);

 92     }

 93     else

 94     {

 95         head = head2;

 96         head->next = MergeRecursive(head1, head2->next);

 97     }

 98

 99     return head;

100 }

101

102 int main(void)

103 {

104     return 0;

105 }