记得以前写过一个合并两个有序数组的问题,也就是相互比较并放入合适的位置,今天的这个算法和数组的问题其实是一样的,这里不多做介绍了,直接贴出代码:
链表的定义:
typedef struct _Node { int data; struct _Node *next; }Node, *List;
首先给出非递归版本的:
合并代码:
List merge_two_list(List list1, List list2) { List new_list = NULL; Node *temp = NULL; if (list1 == NULL) return list2; if (list2 == NULL) return list1; if (list1 -> data <= list2 -> data) { new_list = list1; list1 = list1 -> next; } else { new_list = list2; list2 = list2 -> next; } temp = new_list; while (list1 != NULL && list2 != NULL) { if (list1 -> data <= list2 -> data) { temp -> next = list1; temp = list1; list1 = list1 -> next; } else { temp -> next = list2; temp = list2; list2 = list2 -> next; } } if (list1 != NULL) temp -> next = list1; if (list2 != NULL) temp -> next = list2; return new_list; }
递归版本的代码:
List merge_two_list_2(List list1, List list2) { List new_list = NULL; if (list1 == NULL) return list2; if (list2 == NULL) return list1; if (list1 -> data <= list2 -> data) { new_list = list1; new_list -> next = merge_two_list_2(list1 -> next, list2); } else { new_list = list2; new_list -> next = merge_two_list_2(list1, list2 -> next); } return new_list; }
打印链表节点:
void print(List list_head) { Node *temp = NULL; if (list_head == NULL) return; temp = list_head; while (temp != NULL) { printf("%d ", temp -> data); temp = temp -> next; } }