1：已知两个链表head1和head2各自有序，请把它们合并成一个链表，依然有序。使用非递归方法以及递归方法。
2：首先介绍非递归方法。局部引用方法：这种方法避免使用虚拟节点(dummy node)，而是使用一个指向指针的指针，struct node** lastPtrRef，这个指针指向结果链表的最后一个节点。在这个方法中，所有由虚拟节点完成的工作都有lastPtrRef完成。代码如下：
// ConsoleApplication15.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" #include <malloc.h> #include <iostream> #include <assert.h> using namespace std; typedef struct node//定义链表结构体 { int data;//节点内容 node *next;//指向结构体的指针，下一个节点 }node; node *create()//创建单链表 { int i = 0;//链表中数据的个数 node *head, *p, *q;//这些的本质是节点的地址 int x = 0; head = NULL; q = NULL;//初始化q，q代表末节点 p = NULL; while (1) { printf("please input the data:"); scanf_s("%d", &x); if (x == 0) break;//data为0时创建结束 p = (node *)malloc(sizeof(node));//用于每次输入链表的数据 p->data = x; if (++i == 1)//链表头的指针指向下一个节点 { head = p; q = p; } else { q->next = p;//连接到链表尾端 q = p; } q->next = NULL;/*尾结点的后继指针为NULL(空)*/ } return head; } int length(node *head) { int len = 0; node *p; p = head->next; while (p != NULL) { len++; p = p->next; } return len; } void print(node *head) { node *p; p = head; while (p)/*直到结点q为NULL结束循环*/ { printf("%d ", p->data);/*输出结点中的值*/ p = p->next;/*指向下一个结点*/ } } node *search_node(node *head, int pos)//查找单链表pos位置的节点，返回节点的指针。pos从0开始，0返回head节点 { node *p = head->next; if (pos < 0)//pos位置不正确 { printf("incorrect position to search node!");//pose位置不正确 return NULL; } if (pos == 0) { return head; } if (pos == NULL) { printf("Link is empty!");//链表为空 return NULL; } while (--pos) { if ((p = p->next) == NULL) { printf("incorrect position to search node!");//超出链表返回 break; } } return p; } node *insert_node(node *head, int pos, int data)//单链表的插入 { node *item = NULL; node *p; item = (node *)malloc(sizeof(node)); item->data = data; if (pos == 0)//插在head后面 { head->next = item;//head后面是item return head; } p = search_node(head, pos);//获得pos的节点指针 if (p != NULL) { item->next = p->next;//item指向原pos节点的后一个节点 p->next = item;//把item插入到pos的后面 } return head; } node *delete_node(node *head, int pos)//删除节点 { node *item = NULL; node *p = head->next; if (p = NULL) { printf("link is empty!"); return NULL; } p = search_node(head, pos - 1);//获得位置pos节点的指针 if (p != NULL&&p->next != NULL) { item = p->next; p->next = item->next; delete item; } return head; } node *reverse(node *head)//链表的逆置 { node *next; node *prev = NULL; while (head != NULL) { next = head->next; head->next = prev; prev = head; head = next; } return prev; } node *search(node *head)//寻找单链表的中间元素 { int i = 0; int j = 0; node *current = NULL; node *middle = NULL; current = middle = head->next; while (current != NULL) { if (i / 2 > j) { j++; middle = middle->next; } i++; current = current->next; } return middle; } node *InsertSort(void)//单链表的正向排序 { int data = 0; struct node *head = NULL, *New, *Cur, *Pre=NULL; while (1) { printf("please input the data "); scanf_s("%d", &data); if (data == 0) { break; } New = (struct node*)malloc(sizeof(struct node)); New->data = data; New->next = NULL; if (head == NULL)//第一次循环时对头节点赋值 { head = New; continue; } if (New->data <= head->data) {//head之前插入节点 New->next = head; head = New; continue; } Cur = head; while (New->data > Cur->data && Cur->next != NULL)//找到需要插入的位置 { Pre = Cur; Cur = Cur->next; } if (Cur->data >= New->data)//位置在中间 { Pre->next = New; New->next = Cur; } else//位置在末尾 Cur->next = New;//把New节点插到Cur之后 } return head; } bool IsLoop(node *head, node **start)//判断链表是否存在环形链表，start为回环开始节点的地址 { node *p1 = head, *p2 = head; if (head == NULL || head->next == NULL)//head为NULL或者链表为空时返回false { return false; } do { p1 = p1->next;//p1走一步 p2 = p2->next->next;//p2走两步 } while (p2 && p2->next && p1 != p2); if (p1 == p2) { *start = p1;//p1为回环开始节点 return true; } else { return false; } } void MoveNode(struct node** destRef, struct node** sourceRef)//用于局部引用方法合并有序链表 { /* the front source node */ struct node* newNode = *sourceRef; assert(newNode != NULL); /*Advance the source pointer */ *sourceRef = newNode->next; /* Link th eold dest off the new node */ newNode->next = *destRef; /*Move dest to point to the new node */ *destRef = newNode; } struct node* SortedMerge(struct node* a, struct node* b)//局部引用方法合并有序链表 { struct node* result = NULL; /*point to the last result pointer */ struct node** lastPtrRef = &result; while (1) { if (a == NULL) { *lastPtrRef = b; break; } else if (b == NULL) { *lastPtrRef = a; break; } if (a->data <= b->data) { MoveNode(lastPtrRef, &a); } else { MoveNode(lastPtrRef, &b); } /*tricky:advance to point to the next ".next" field */ lastPtrRef = &((*lastPtrRef)->next); } return (result); } int main() { node *head1 = create();//创建单链表1 node *head2 = create();//创建单链表2 node *head = SortedMerge(head1, head2); print(head); return 0; }
运行结果：
3：递归方法如下：
// ConsoleApplication15.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" #include <malloc.h> #include <iostream> using namespace std; typedef struct node//定义链表结构体 { int data;//节点内容 node *next;//指向结构体的指针，下一个节点 }node; node *create()//创建单链表 { int i = 0;//链表中数据的个数 node *head, *p, *q;//这些的本质是节点的地址 int x = 0; head = NULL; q = NULL;//初始化q，q代表末节点 p = NULL; while (1) { printf("please input the data:"); scanf_s("%d", &x); if (x == 0) break;//data为0时创建结束 p = (node *)malloc(sizeof(node));//用于每次输入链表的数据 p->data = x; if (++i == 1)//链表头的指针指向下一个节点 { head = p; q = p; } else { q->next = p;//连接到链表尾端 q = p; } q->next = NULL;/*尾结点的后继指针为NULL(空)*/ } return head; } int length(node *head) { int len = 0; node *p; p = head->next; while (p != NULL) { len++; p = p->next; } return len; } void print(node *head) { node *p; p = head; while (p)/*直到结点q为NULL结束循环*/ { printf("%d ", p->data);/*输出结点中的值*/ p = p->next;/*指向下一个结点*/ } } node *search_node(node *head, int pos)//查找单链表pos位置的节点，返回节点的指针。pos从0开始，0返回head节点 { node *p = head->next; if (pos < 0)//pos位置不正确 { printf("incorrect position to search node!");//pose位置不正确 return NULL; } if (pos == 0) { return head; } if (pos == NULL) { printf("Link is empty!");//链表为空 return NULL; } while (--pos) { if ((p = p->next) == NULL) { printf("incorrect position to search node!");//超出链表返回 break; } } return p; } node *insert_node(node *head, int pos, int data)//单链表的插入 { node *item = NULL; node *p; item = (node *)malloc(sizeof(node)); item->data = data; if (pos == 0)//插在head后面 { head->next = item;//head后面是item return head; } p = search_node(head, pos);//获得pos的节点指针 if (p != NULL) { item->next = p->next;//item指向原pos节点的后一个节点 p->next = item;//把item插入到pos的后面 } return head; } node *delete_node(node *head, int pos)//删除节点 { node *item = NULL; node *p = head->next; if (p = NULL) { printf("link is empty!"); return NULL; } p = search_node(head, pos - 1);//获得位置pos节点的指针 if (p != NULL&&p->next != NULL) { item = p->next; p->next = item->next; delete item; } return head; } node *reverse(node *head)//链表的逆置 { node *next; node *prev = NULL; while (head != NULL) { next = head->next; head->next = prev; prev = head; head = next; } return prev; } node *search(node *head)//寻找单链表的中间元素 { int i = 0; int j = 0; node *current = NULL; node *middle = NULL; current = middle = head->next; while (current != NULL) { if (i / 2 > j) { j++; middle = middle->next; } i++; current = current->next; } return middle; } node *InsertSort(void)//单链表的正向排序 { int data = 0; struct node *head = NULL, *New, *Cur, *Pre=NULL; while (1) { printf("please input the data "); scanf_s("%d", &data); if (data == 0) { break; } New = (struct node*)malloc(sizeof(struct node)); New->data = data; New->next = NULL; if (head == NULL)//第一次循环时对头节点赋值 { head = New; continue; } if (New->data <= head->data) {//head之前插入节点 New->next = head; head = New; continue; } Cur = head; while (New->data > Cur->data && Cur->next != NULL)//找到需要插入的位置 { Pre = Cur; Cur = Cur->next; } if (Cur->data >= New->data)//位置在中间 { Pre->next = New; New->next = Cur; } else//位置在末尾 Cur->next = New;//把New节点插到Cur之后 } return head; } bool IsLoop(node *head, node **start)//判断链表是否存在环形链表，start为回环开始节点的地址 { node *p1 = head, *p2 = head; if (head == NULL || head->next == NULL)//head为NULL或者链表为空时返回false { return false; } do { p1 = p1->next;//p1走一步 p2 = p2->next->next;//p2走两步 } while (p2 && p2->next && p1 != p2); if (p1 == p2) { *start = p1;//p1为回环开始节点 return true; } else { return false; } } struct node* SortedMerge(struct node* a, struct node* b)//将两个链表合并，递归法 { struct node* result = NULL; /*Base cases*/ if (a == NULL) return (b); else if (b == NULL) return (a); /*Pick either a or b, and recur */ if (a->data <= b->data) { result = a; result->next = SortedMerge(a->next, b); } else { result = b; result->next = SortedMerge(a, b->next); } return (result); } int main() { node *head1 = create();//创建单链表1 node *head2 = create();//创建单链表2 node *head = SortedMerge(head1, head2); print(head); return 0; }
运行结果：
