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

题目

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

难度

士 ★☆☆☆

解答

本题难度很低,因为是有序链表,所以从两个链表的头开始进行如下判断:

  • 如果 head1 的值小于 head2,则 head1 往下移动。
  • 如果 head2 的值小于 head1,则 head2 往下移动。
  • 如果 head1 的值与 head2 的值相等,则打印这个值,然后 head1 和 head2 都往下移动。
  • head1 或 head2 有任何一个移动到 null,整个过程停止。

具体过程参考如下代码中的 printCommonPart 方法:

struct Node{
   int value;
   struct Node* next;
   
   Node(int data): value(data), next(NULL) {}
};

class List
{
private:
   Node* head;
   Node* tail;
public:
   List(): head(NULL), tail(NULL) {}
   void add(int value);
   Node* getHead();
   Node* getTail();
};

Node* List::getHead()
{
   return this->head;
}

Node* List::getTail()
{
   return this->tail;
}

void List::add(int value)
{
   Node *node = new Node(value);
   if (this->head == NULL) {
       this->head = node;
       this->tail = node;
   } else {
       this->tail->next = node;
       this->tail = this->tail->next;
   }
}

void printCommonPart(Node *head1, Node *head2)
{
   while (head1 != NULL && head2 != NULL) {
       if (head1->value < head2->value) {
           head1 = head1->next;
       } else if (head1->value > head2->value) {
           head2 = head2->next;
       } else {
           cout << head1->value << endl;
           head1 = head1->next;
           head2 = head2->next;
       }
   }
}


int main(int argc, const char * argv[]) {
   List *l1 = new List();
   for (int i = 0; i < 5; i ++) {
       l1->add(i);
   }
   
   List *l2 = new List();
   for (int i = 2; i < 10; i ++) {
       l2->add(i);
   }
   
   printCommonPart(l1->getHead(), l2->getHead());
   
   return 0;
}

运行结果

2
3
4
Program ended with exit code: 0
Last modification:February 9th, 2020 at 07:03 pm
如果觉得我的文章对你有用,请随意赞赏