这里数据域设为int类型，其实String也是一样的
思路一：
1.对于链表str1和str2，分别求出两个链表的长度m和n，
2。p指向str1的头节点，q指向str2的头节点，当m大于等于n，p向后移动m-n+1个节点，当n大于m，q向后移n-m+1，总之，要保证p和q所指的节点到链表尾的长度相等。
3.反复将指针p和q同步后移，并判断它们是否指向同一个节点，若指向同一点，则返回共同后缀的起始位置
</pre><pre name="code" class="java">package pac1; class Node{ public Node next; //指针域 public int data; //数据域 public Node(int data) { this.data = data; } public void show(){ System.out.print(data+" "); } } public class LinkList { public Node head; //头节点 public LinkList(){ this.head=null; } //头插法创建表，将新节点插入到头结点之后 public void creatList1(LinkList L,int [] arr){ for(int i=0;i<arr.length;i++){ Node node=new Node(arr[i]); //创建一个新节点 node.next = head; head = node; } } //尾插法创建表 public void creatList2(LinkList L,int [] arr){ addHeadNode(arr[0]);//将第一个元素作为头结点 Node rear=head; for(int i=1;i<arr.length;i++){ Node node=new Node(arr[i]); //创建一个新节点 rear.next= node; rear=node; } } //显示表 public void showList(){ Node current=head; while(current!=null){ current.show(); current=current.next; } System.out.println(); } //求两个链表的共同后缀的起始位置 public int findList(LinkList str1,LinkList str2){ int m=0; Node p=str1.head; while(p!=null){ //计算str1的长度 m++; p=p.next; } Node q=str2.head; int n=0; while(q!=null){ //计算str2的长度 n++; q=q.next; } p=str1.head; q=str2.head; if(n>m){ //当str2较长时，q向后移，保证p和q所指的节点到表尾的长度相等 q=str2.head; int j=0; while(j<n-m){ j++; q=q.next; } } else{ //当str1较长时，p向后移，保证p和q所指的节点到表尾的长度相等 p=str2.head; int k=0; while(k<m-n){ k++; p=p.next; } } int mov=0; //注意这里比较的是节点的地址，而不是节点的值 while(p.next!=null && q.next!=null && p.next!=q.next){ p=p.next; q=q.next; mov++; } int res=0; if(n>m) res=n-m+mov; else res=m-n+mov; return res; } //思路二：串模式匹配算法 public int findList2(LinkList str1,LinkList str2){ Node p=str1.head; Node q; int i=0,res=0; while(p!=null){ i++; q=str2.head; while(q!=null){ if(q==p) {res=i;break;} q=q.next; } p=p.next; } return res; } /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub int [] arr={1,2,3,4,5}; LinkList L=new LinkList(); L.creatList2(L, arr); L.showList(); // int [] arr2={7,8,4,5}; LinkList L2=new LinkList(); L2.creatList2(L2, arr2); L2.showList(); System.out.println(L.findList1(L, L2)); } }
思路一的时间复杂度是O(m+n)
思路二：采用串模式匹配的思想。p指向str1，q指向str2，遍历str2，查找str2是否有和p指向的当前节点相同的节点。
现在存在的问题：
思路一可正常运行，通过p.next!=q.next 比较节点的地址是成立的，在思路二中当p、q指向的节点都是4时,判断条件p==q仍然为false，显然p和q指向的不是同一地址，但是p.next和q.next是可以判断出指向的是同一地址，不知其所以然。
