程序员代码面试指南 2.1：打印两个升序链表的公共部分

1、思路

打印所有公共的部分，不止是连续的公共部分，用两个指针a与b从头遍历两个升序链表：

• 若a的值小于b，则a往下移动；

• 若b的值小于a，则b往下移动；

• 若a的值等于b，则打印该值，且两个指针都往下移动一步。

2、代码

#include <iostream>
#include <memory>    //包含了智能指针库

using namespace std;

struct ListNode{
    int val;
    shared_ptr<ListNode> next;
    ListNode(int _val) : val(_val), next(nullptr) {}    //构造函数
}; 

shared_ptr<ListNode> createList()                       //构造链表
{
    int n, val;
    cin >> n;

    shared_ptr<ListNode> head = make_shared<ListNode>(0);
    auto cur = head;

    while (n -- )
    {
        cin >> val;
        cur = cur->next = make_shared<ListNode>(val);
    }

    return head->next;
}

void sol(shared_ptr<ListNode> a_head, shared_ptr<ListNode> b_head)  //打印升序链表的公共部分
{
    while (a_head != nullptr && b_head != nullptr)
    {
        if (a_head->val > b_head->val)
        {
            b_head = b_head->next;
        }
        else if (a_head->val < b_head->val)
        {
            a_head = a_head->next;
        }
        else
        {
            cout << a_head->val << " ";
            a_head = a_head->next, b_head = b_head->next;   //同时往下移动
        }
    }
}

int main ()
{
    shared_ptr<ListNode> a_head = createList(); // A 链表的头节点
    shared_ptr<ListNode> b_head = createList(); // B 链表的头节点
    sol(a_head, b_head);
    return 0;
}