打印两个有序链表的公共部分

【说明】：

　　本文是左程云老师所著的《程序员面试代码指南》第二章中“打印两个有序链表的公共部分”这一题目的C++复现。

　　本文只包含问题描述、C++代码的实现以及简单的思路，不包含解析说明，具体的问题解析请参考原书。

　　感谢左程云老师的支持。

【题目】：

　　给定两个有序链表的头指针 head1 和 head2，打印两个链表的公共部分。

【思路】：

　　依次比较

【编译环境】：

　　CentOS6.7（x86_64）

　　gcc 4.4.7

【实现】：

　　实现及测试代码：

 1 /*
 2  *文件名：comPart.cpp
 3  *作者：
 4  *摘要：打印两个有序链表的公共部分
 5  */
 6  
 7 #include <iostream>
 8 
 9 using namespace std;
10 
11 struct Node
12 {
13     int value;
14     Node *next;
15 };
16 
17 void printComPart(Node *head1,Node *head2)
18 {
19     cout << "Common Part: " << endl;
20     while(NULL != head1 && NULL != head2)
21     {
22         if(head1->value < head2->value)
23             head1 = head1->next;
24         else if(head1->value > head2->value)
25             head2 = head2->next;
26         else
27         {
28             cout << head1->value << " " ;
29             head1 = head1->next;
30             head2 = head2->next;
31         }
32     }
33     cout << endl;
34 }
35 
36 int main()
37 {
38     Node *head1 = NULL;
39     Node *head2 = NULL;
40     Node *ptr = NULL;
41     
42     for(int i =0;i<10;i++)
43     {
44         if(NULL == head1)
45         {    
46             head1 = new Node;
47             head1->value = i;
48             head1->next = NULL;
49             ptr = head1;
50             continue;
51         }
52         ptr->next = new Node;
53         ptr = ptr->next;
54         ptr->value = i;
55         ptr->next = NULL;
56     }
57     for(int i =3;i<23;i++)
58     {
59         if(NULL == head2)
60         {    
61             head2 = new Node;
62             head2->value = i;
63             head2->next = NULL;
64             ptr = head2;
65             continue;
66         }
67         ptr->next = new Node;
68         ptr = ptr->next;
69         ptr->value = i;
70         ptr->next = NULL;
71     }
72     printComPart(head1,head2);
73     return 0;
74 }

View Code

注：

　　转载请注明出处；

　　转载请注明源思路来自于左程云老师的《程序员代码面试指南》。