【算法题】2.求两个链表的交集

题目

已知两个链表A和B分别表示两个集合.其元素递增排列。设计一个算法,用于求出A与B的交集,并存储在A链表中。

题目大意：

取链表A与链表B值相同的结点，存储在A链表中。

输入：

2->4->6->8,4->6->8->10

输出：

4->6->8

解析：

迭代法比较，释放较小结点。

1. 存储在A链表，维护一个新的 l3指针,指向A的头结点，两个临时指针p1与p2指向 A与B链表，开始迭代。
2. 临时Temp指针指向较小者，将较小者向后移一个，释放Temp指向的空间
3. 若两者相同，取其中一个接在p3的结点后面，释放另外一个相同结点，同时将两个指针向后移一个，直到p1或p2为空。
4. 迭代完后，将p3的Next指向NULL
5. 释放非空指针，释放B的头结点。

复杂度分析

时间复杂度：
空间复杂度：

代码

LinkList IntersectionOfTwoLists(LinkList *A, LinkList *B){
  
    if (A == NULL)
    {    
     return NULL;
    }
    if (B == NULL)
    {
     return NULL;
    }
    

    ListNode *p1 = (*A)->next;
    ListNode *p2 = (*B)->next;
    ListNode *result = (*A);
    ListNode *p3 = (*A);
   
    while(p1!= NULL && p2 != NULL){
      
      int pVal = p1->data;
      int p2Val = p2->data;
      printf("p---%d,q---%d\n", pVal,p2Val);
       if (pVal > p2Val)
       {

           ListNode *temp = p2;
           p2 = p2->next;
          free(temp);
       }else if (pVal < p2Val)
       {
            ListNode *temp = p1;
           p1 = p1->next;
           free(temp);
       }else{
          p3->next = p1;
          p3 = p1;
          p1 = p1->next;
           ListNode *temp = p2;
          p2 = p2->next;
          free(temp);
       }
      
    }

    p3->next = NULL;
    if (p2)
    {
       free(p2);
    }else if (p1)
    {
       free(p1);
    }
    free(*B);
 return result;
}