首页 / 软件开发 / 数据结构与算法 / 微软面试题解析：请修改append函数， 利用函数实现（链表）

微软面试题解析：请修改append函数， 利用函数实现（链表）2014-12-24题目：

请修改append函数，利用这个函数实现：

两个非降序链表的并集，1->2->3 和 2->3->5 并为 1->2->3->5

另外只能输出结果，不能修改两个链表的数据。

分析：

这题很简单，两个指向链表的指针，比较对应的值，并遍历

实现如下：

#include<iostream>using namespace std;struct Node{Node（int _v = 0）:value（_v）,next（NULL） {}int value;Node *next;};void printNodes（Node* n1, Node* n2）{Node* p1 = n1;Node* p2 = n2;while（p1 ！= NULL && p2 ！= NULL）{if（p1->value < p2->value）{cout << p1->value << "->";p1 = p1->next;}else if（p1->value > p2->value）{cout << p2->value << "->";p2 = p2->next;}else{if（p1->next == NULL && p2->next == NULL）cout << p2->value << endl;elsecout << p2->value << "->";p2 = p2->next;p1 = p1->next;}}while（p1 ！= NULL）{if（p1->next == NULL）cout << p1->value << endl;elsecout << p1->value << "->";p1 = p1->next;}while（p2 ！= NULL）{if（p2->next == NULL）cout << p2->value << endl;elsecout << p2->value << "->";p2 = p2->next;}}int main（）{Node n1（1）, n2（2）, n3（3）, n4（2）, n5（3）, n6（5）;Node* node1 = &n1;node1->next = &n2;node1->next->next = &n3;Node* node2 = &n4;node2->next = &n5;node2->next->next = &n6;cout << "list1: ";printNodes（node1, NULL）;cout << "list2: ";printNodes（node2, NULL）;cout << "list1 and list2: ";printNodes（node1, node2）;return 0;}

输出如下：

list1: 1->2->3

list2: 2->3->5

list1 and list2: 1->2->3->5

作者：csdn博客 hhh3h