题目
解决代码及点评
- <pre code_snippet_id="112572" snippet_file_name="blog_20131214_1_2199083" class="cpp" name="code"><pre code_snippet_id="112572" snippet_file_name="blog_20131214_1_2199083" class="cpp" name="code"><pre code_snippet_id="112572" snippet_file_name="blog_20131214_1_2199083" class="cpp" name="code"><pre code_snippet_id="112572" snippet_file_name="blog_20131214_1_2199083" name="code" class="cpp"><pre code_snippet_id="112572" snippet_file_name="blog_20131214_1_2199083" name="code" class="cpp">/*
- 两个升序链表合并,并要求去掉重复元素
- */
- #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");
- }</pre><br></pre><br><br></pre></pre></pre>
代码下载及其运行代码下载地址:http://download.csdn.net/detail/yincheng01/6704519
解压密码:c.itcast.cn
下载代码并解压后,用VC2013打开interview.sln,并设置对应的启动项目后,点击运行即可,具体步骤如下: 1)设置启动项目:右键点击解决方案,在弹出菜单中选择“设置启动项目”
2)在下拉框中选择相应项目,项目名和博客编号一致
3)点击“本地Windows调试器”运行
程序运行结果
|