C和C++程序员面试秘笈:32---合并两个有序单链表

一、题目要求

* 现在有2条单链表，都是有序排列的（从小到大），现在要你将两条单链表合并为1条单链表，合并后链表依然有序
* 例如：
* list1为1、3、5
* list2为2、4、6
* 将list1和list2合并为新链表list3，值为1、2、3、4、5、6
二、编码实现
/** * @description: 将temp节点插入到head所指的链表中 * @param: head: 要插入的链表的起始位置 temp:
要插入的链表的节点指针 * @return: 返回插入后形成的链表的头结点 * @author: Dongshao */ Node
*insert_node(Node *head, Node *temp) { Node *p = head; Node *q = NULL; //
只要q不比p所指的节点的值小, 那么就往后遍历 while(p->_data < temp->_data && p != NULL) { q = p; p =
p->_pNext; } // 如果p等于head, 说明temp比head所指链表的所有节点都小, 那么将temp插入到head之前,
直接返回temp就可以了 if(p == head) { temp->_pNext = p; return temp; } //
否则就将temp插入到head所指的链表的中间 q->_pNext = temp; temp->_pNext = p; return head; } /**
* @description: 合并两个有序链表(从小到大) * @param : list1: 第1个链表 list2: 第2个链表 * @return:
返回合并后链表的头结点 * @author: Dongshao */ Node *merge2List(Node *list1, Node *list2) {
// 如果哪条链表为空, 那么就返回另外一条链表 if (list1 == NULL) return list2; if (list2 == NULL)
return list1; Node *head; // 一开始指向较长链表 Node *p; // 一开始指向较短链表 Node *q; //
指向与p之后的节点 // 链表1比链表2长 if (listLength(list1) >= listLength(list2)) { head =
list1->_pNext; p = list2->_pNext; } else { head = list2->_pNext; p =
list1->_pNext; } // 哪个链表短, 就循环把哪个短链表插入到长链表中 while (p != NULL) { q = p->_pNext;
// 先保存下一节点 head = insert_node(head, p); // 将p插入到head所指的链表中 p = q; } //
返回新形成链表的头结点 return head; } /** * @description: 返回链表的长度 * @param: _head: 链表的头结点
* @return: 返回链表的长度 * @author: Dongshao */ size_t listLength(Node *_head) { if
(_head == NULL || _head->_pNext == NULL) return 0; size_t count; Node *temp =
_head->_pNext; while (temp != NULL) { count++; temp = temp->_pNext; } return
count; }
三、测试

* 测试代码如下 #include <stdio.h> #include <stdlib.h> typedef struct node { struct
node *_pNext; int _data; } Node; Node *insert_node(Node *head, Node *temp);
Node *merge2List(Node *list1, Node *list2); Node *createList(int num); void
showList(Node *_head); size_t listLength(Node *_head); void freeList(Node
*_head); /** * @description: 将temp节点插入到head所指的链表中 * @param: head: 要插入的链表的起始位置
temp: 要插入的链表的节点指针 * @return: 返回插入后形成的链表的头结点 * @author: Dongshao */ Node
*insert_node(Node *head, Node *temp) { Node *p = head; Node *q = NULL; //
只要q不比p所指的节点的值小, 那么就往后遍历 while(p->_data < temp->_data && p != NULL) { q = p; p =
p->_pNext; } // 如果p等于head, 说明temp比head所指链表的所有节点都小, 那么将temp插入到head之前,
直接返回temp就可以了 if(p == head) { temp->_pNext = p; return temp; } //
否则就将temp插入到head所指的链表的中间 q->_pNext = temp; temp->_pNext = p; return head; } /**
* @description: 合并两个有序链表(从小到大) * @param : list1: 第1个链表 list2: 第2个链表 * @return:
返回合并后链表的头结点 * @author: Dongshao */ Node *merge2List(Node *list1, Node *list2) {
// 如果哪条链表为空, 那么就返回另外一条链表 if (list1 == NULL) return list2; if (list2 == NULL)
return list1; Node *head; // 一开始指向较长链表 Node *p; // 一开始指向较短链表 Node *q; //
指向与p之后的节点 // 链表1比链表2长 if (listLength(list1) >= listLength(list2)) { head =
list1->_pNext; p = list2->_pNext; } else { head = list2->_pNext; p =
list1->_pNext; } // 哪个链表短, 就循环把哪个短链表插入到长链表中 while (p != NULL) { q = p->_pNext;
// 先保存下一节点 head = insert_node(head, p); // 将p插入到head所指的链表中 p = q; } //
返回新形成链表的头结点 return head; } /** * @description: 创建链表 * @param: num: 链表节点数量 *
@return: 创建新链表的头指针 * @author: Dongshao */ Node *createList(int num) { if (num <
0) return NULL; Node *_head = (Node *)malloc(sizeof(Node)); _head->_pNext =
NULL; Node *_tempHead = _head; Node *_newNode; for (int i = 0; i < num; ++i) {
// 创建新节点 _newNode = (Node *)malloc(sizeof(Node)); _newNode->_data = (i + 1);
_newNode->_pNext = NULL; // 向后偏移 _tempHead->_pNext = _newNode; _tempHead =
_newNode; _newNode = NULL; } return _head; } /** * @description: 打印链表 * @param:
_head: 链表的头结点 * @return: 无 * @author: Dongshao */ void showList(Node *_head) {
if (_head == NULL) return; Node *_tempNode = _head; // 循环打印 while (_tempNode !=
NULL) { if (_tempNode->_pNext == NULL) break; else printf("%d->",
_tempNode->_data); _tempNode = _tempNode->_pNext; } // 打印最后一个节点的 printf("%d\n",
_tempNode->_data); } /** * @description: 返回链表的长度 * @param: _head: 链表的头结点 *
@return: 返回链表的长度 * @author: Dongshao */ size_t listLength(Node *_head) { if
(_head == NULL || _head->_pNext == NULL) return 0; size_t count; Node *temp =
_head->_pNext; while (temp != NULL) { count++; temp = temp->_pNext; } return
count; } /** * @description: 销毁链表 * @param: _head: 链表的头结点 * @return: 无 *
@author: Dongshao */ void freeList(Node *_head) { if (_head == NULL ||
_head->_pNext == NULL) return; Node *temp1 = _head->_pNext; Node *temp2; while
(temp1 != NULL) { temp2 = temp1->_pNext; free(temp1); temp1 = temp2; } } int
main() { Node *list1 = NULL, *list2 = NULL; // 创建链表, 并打印链表 list1 =
createList(3); list2 = createList(3); // 伪造第一个链表, 将其值改为1、3、5
list1->_pNext->_data = 1; list1->_pNext->_pNext->_data = 3;
list1->_pNext->_pNext->_pNext->_data = 5; // 伪造第二个链表, 将其值改为2、4、6
list2->_pNext->_data = 2; list2->_pNext->_pNext->_data = 4;
list2->_pNext->_pNext->_pNext->_data = 6; showList(list1->_pNext);
showList(list2->_pNext); // 反转链表, 并打印链表 Node *list3 = merge2List(list1, list2);
showList(list3); // 释放链表 freeList(list1); freeList(list2); return 0; }
* 结果如下：

• « 上一篇：大厂Java面试题解(45)-设计一个高并发系统
• » 下一篇：VUE组件传值案例讲解