链表交并差

一、问题描述　

　　两个有序的无头节点的链表La，Lb。编写函数：如何以最优的方式找出二者的交集，并且把结果存在一个新链表中返回。

二、算法思想

　　定义两个指针分别遍历La和Lb，因为两个链表是有序的所以当指针pa*和pb*中值相同时，加入新链表，然后同时后移一个位置。当pa*和pb*值不同时就让小的那个后移，继续比较值。让其中一个指针的next为空时就返回结果。

三、核心代码

　　

 1 ListNode* intersection(ListNode *A,ListNode *B){
 2     ListNode* pa=A,pb=B;
 3     LNode C = new LNode;
 4     ListNode* pc=C;
 5     if(A == null){
 6         return B;        
 7     }else if(B == null){
 8         return A;
 9     }
10     while(pa != null||pb != null){
11         if(pa->data == pb->data){
12             p = new LNode;
13             p->data=pa->data;
14             pc->next = p;
15             pc = pc->next;
16             pa=pa->next;
17             pb=pb->next;
18         }else if(pa->data<pb->data){
19             pa=pa->next;
20         }else(
21             pb=pb->next;
22         )
23     }
24     return C;
25 }