采用带头节点的单链表保存单词，返回两个链表共同后缀的起始位置

这里数据域设为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是可以判断出指向的是同一地址，不知其所以然。