左神算法基础class3—题目10打印两个有序链表的公共部分

本文主要是介绍左神算法基础class3—题目10打印两个有序链表的公共部分，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

左神算法基础class3—题目10打印两个有序链表的公共部分

1.题目
2.分析
3.核心代码
- (1)链表的建立
- (2)外排过程
4.完整代码
5.输出结果

1.题目

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

2.分析

打印链表的公共部分类似外排方式（外排不了解的请点击查看算法流程3），原理如下：设置两个指针分别指向链表1和链表2的第一个数，比较指针所指的数的大小
（1）如果链表1的数字小，则链表1的指针后移，指向后一个数；
（2）如果链表2的数字小，则链表2的指针后移，指向后一个数；
（3）如果两个数相等就打印输出当前数，并把指针1,2都向后移一位。

3.核心代码

(1)链表的建立

①数据结构由指针域和数据域构成

typedef struct ListNode
{int val;ListNode *next;
}*List;

②初始化头节点，注意此处不能写为head1 = NULL

List head1 = (List)malloc(sizeof(ListNode));head1->next = NULL;

③使用尾插法初始化，新的节点为p1，而尾节点是r，初始指向头节点，对p1初始化后把尾节点指向新节点连接构成链表，再把当前节点设置为尾节点，继续新初始化p1不断循环。最后把尾节点指向空，链表就初始化完成。

List r1,r2,p1,p2;r1 = head1;r2 = head2;//初始化head1（1,2,3,4）for(int i = 0;i < 4;i++){p1 = (List)malloc(sizeof(ListNode));p1->val = i + 1;r1->next = p1;r1 = p1;}r1->next = NULL;

(2)外排过程

外排条件是当一方链表走到头结束。
注意继续查找的条件是head1 != NULL && head2 != NULL，而不能写成head1->val != NULL && head2 ->val!= NULL

void merge(List head1,List head2)
{while(head1 != NULL && head2 != NULL){if(head1->val < head2->val){head1 = head1->next;}else if(head1->val > head2->val){head2 = head2->next;}else{cout<<head1->val<<" ";head1 = head1->next;head2 = head2->next;}}
}

4.完整代码

#include<iostream>
using namespace std;typedef struct ListNode
{int val;ListNode *next;
}*List;void merge(List head1,List head2)
{while(head1 != NULL && head2 != NULL){if(head1->val < head2->val){head1 = head1->next;}else if(head1->val > head2->val){head2 = head2->next;}else{cout<<head1->val<<" ";head1 = head1->next;head2 = head2->next;}}
}int main()
{List head1 = (List)malloc(sizeof(ListNode));head1->next = NULL;List head2 = (List)malloc(sizeof(ListNode));head2->next = NULL;List r1,r2,p1,p2;r1 = head1;r2 = head2;//初始化head1（1,2,3,4）for(int i = 0;i < 4;i++){p1 = (List)malloc(sizeof(ListNode));p1->val = i + 1;r1->next = p1;r1 = p1;}r1->next = NULL;//初始化head2（0,2,4,6）for(int i = 0;i < 4;i++){p2 = (List)malloc(sizeof(ListNode));p2->val = i * 2;r2->next = p2;r2 = p2;}r2->next = NULL;merge(head1->next,head2->next);system("pause");return 0;}