N36_两个链表的第一个公共结点。

客官°小女子只卖身不卖艺 2023-08-17 17:36 114阅读 0赞

## 题目描述 ##

输入两个链表，找出它们的第一个公共结点。

package new_offer;
    /**
     * 输入两个链表，找出它们的第一个公共结点。
     * @author Sonya
     *思路：首先有公共节点的两个链表是Y型。先遍历两个链表得到长度
     *长的就多走长度之差步。然后遍历两个链表 得到第一个公共节点。
     */
    /*
    public class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }*/
    public class N36_FindFirstCommonNode {
    	public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
    		ListNode p1,p2;
    		if(pHead1==null||pHead2==null)return null;
    		p1=pHead1;p2=pHead2;
    		int i1=0;
    		int i2=0;
    		while(p1!=null) {i1++;p1=p1.next;System.out.println(i1);}//计算两个链表的长度。
    		while(p2!=null) {i2++;p2=p2.next;System.out.println(i2);}
    		int j=i1-i2;
    		if(j>0) {//1比2长。
    		p1=pHead1;p2=pHead2;
    		for(int i=0;i<j;i++) {p1=p1.next;}//多走J步
    		while(p1!=p2) {
    			p1=p1.next;
    			p2=p2.next;
    		}
    		return p1;
    		}else {
    			p1=pHead1;p2=pHead2;
    			j=0-j;
    			for(int i=0;i<j;i++) {p2=p2.next;}//多走J步
    			while(p1!=p2) {
    				p1=p1.next;
    				p2=p2.next;
    			}
    			return p1;		
    		}
    		
        }
    	public static void main(String[] args) {
    		ListNode listNode=new ListNode(1);
    		ListNode L2=new ListNode(2);
    		ListNode L3=new ListNode(3);
    		ListNode L4=new ListNode(4);
    		ListNode L5=new ListNode(5);
    		listNode.next=L2;
    		L2.next=L3;
    		L3.next=L4;
    		L4.next=L5;
    		//两个头是listnode和L3;
    		 N36_FindFirstCommonNode n36=new  N36_FindFirstCommonNode();
    	ListNode p=n36.FindFirstCommonNode(listNode, listNode);
    	System.out.println("***********");
    	System.out.println(p.val);		
    	}
    }

转载于:https://www.cnblogs.com/kexiblog/p/11157498.html