基于visual Studio2013解决面试题之0402合并升序链表并去重-LMLPHP

题目

解决代码及点评

/*
两个升序链表合并,并要求去掉重复元素
*/
#include <iostream>
using namespace std; class LinkNode
{
public:
int _val;
LinkNode* _next;
LinkNode(int val, LinkNode* next = NULL) :_val(val), _next(next){}
}; class Link
{
public:
LinkNode* _head;
Link() : _head(NULL){} /* 构造有序链表函数 */
void add(int val)
{
/* 如果头节点为空,则直接赋值头结点 */
if (_head == NULL)
{
_head = new LinkNode(val);
return;
} /* 循环找合适的位置,将新的val插入到链表中 */
for (LinkNode* pos = _head; ; pos = pos->_next)
{
/* 如果找到末尾,还没有合适位置,那么新的val插入到尾部 */
if (pos->_next == NULL)
{
pos->_next = new LinkNode(val);
break;
}
/* 如果某个位置的_val > val,那么新的val应该插入到该位置 */
else if (pos->_next->_val > val)
{
LinkNode* node = new LinkNode(val);
node->_next = pos->_next;
pos->_next = node;
break;
}
}
} /* 合并并去除重复节点 */
void merge(const Link& link)
{
LinkNode* pos = _head; // 遍历所有link节点
for (LinkNode* node = link._head; node; node = node->_next)
{
// 找到合适的位置进行插入操作
for (;; pos = pos->_next)
{
/* 如果值相等,那么直接丢弃 */
if (pos->_val == node->_val)
break; /* 如果找到末尾,则把新节点放到末尾 */
if (pos->_next == NULL)
{
pos->_next = new LinkNode(node->_val);
pos = pos->_next;
break;
}
/* 如果找到中间某个位置,那么新节点要插入 */
else if (pos->_next->_val > node->_val)
{
pos->_next = new LinkNode(node->_val, pos->_next);
pos = pos->_next;
break;
}
}
}
} /* 打印所有节点 */
void print()
{
for (LinkNode* node = _head; node; node = node->_next)
{
cout << node->_val << " ";
}
cout << endl;
cout << "****************" << endl;
}
}; int main()
{
Link l1;
l1.add(1);
l1.add(3);
l1.add(5);
l1.add(10);
l1.print(); Link l2;
l2.add(1);
l2.add(5);
l2.add(4);
l2.add(3);
l2.add(6);
l2.print(); l1.merge(l2);
l1.print(); system("pause");
}

代码下载及其运行

代码下载地址:http://download.csdn.net/detail/yincheng01/6704519

解压密码:c.itcast.cn

下载代码并解压后,用VC2013打开interview.sln,并设置对应的启动项目后,点击运行即可,具体步骤如下:

1)设置启动项目:右键点击解决方案,在弹出菜单中选择“设置启动项目”

2)在下拉框中选择相应项目,项目名和博客编号一致

3)点击“本地Windows调试器”运行

程序运行结果





05-11 22:23
查看更多