1:已知两个链表head1和head2各自有序,请把它们合并成一个链表,依然有序。使用非递归方法以及递归方法。
2:首先介绍非递归方法。局部引用方法:这种方法避免使用虚拟节点(dummy node),而是使用一个指向指针的指针,struct node** lastPtrRef,这个指针指向结果链表的最后一个节点。在这个方法中,所有由虚拟节点完成的工作都有lastPtrRef完成。代码如下:
// ConsoleApplication15.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include#include #include 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\n"); 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#include 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\n"); 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;}
运行结果: