求两个链表的第一个公共节点

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

解法思路

介绍了四种解法，复杂度分别是最高的O(n^2）到最低的O(n)，最优解法是解法四。

第一种解法

蛮力（暴力）法，双重循环遍历。
代码

ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        ListNode *p1 = pHead1;
        ListNode *p2 = pHead2;
        for(; p1 != NULL; p1 = p1->next)
        {
            for(p2 = pHead2; p2 != NULL; p2 = p2->next)
                if(p1 == p2)
                    return p1;
        }
        return NULL;
}

第二种解法

借助于栈的先进后出，由于找到两个链表的第一个公共结点，故这个链表在公共结点以后是一个Y字型，故我们将两个链表放入栈中，来找到栈中最后一个相同的结点，即为链表的第一个公共结点。（利用空间来换取时间）

代码

public class Main {
 
	public ListNode findFirstCommonNode(ListNode pHead1, ListNode pHead2){
		Stack<ListNode> s1 = new Stack<ListNode>();
		Stack<ListNode> s2 = new Stack<ListNode>();
		if(pHead1 == null || pHead2 == null){
			return null;
		}
		while(pHead1!=null){
			s1.push(pHead1);
			pHead1 = pHead1.next;
		}
		while(pHead2!=null){
			s2.push(pHead2);
			pHead2 = pHead2.next;
		}
		ListNode l3 = null;
		while(!s1.isEmpty()){
			ListNode l1 = (ListNode) s1.peek();
			ListNode l2 = (ListNode) s2.peek();
			if(l1 == l2){
				l3 = s1.pop();
				s2.pop();
				continue;
			}
			return l3;
		}
		return null;
	}
}

第三种解法

首先遍历两个链表得出两个链表的长度，得出长的链表比短的链表多几个元素，然后长的链表就先走几个元素，然后使其没有遍历的元素和短的链表的元素长度相等。然后再进行遍历，找到第一个公共结点。
代码

public class Main {
 
	public ListNode findFirstCommonNode(ListNode pHead1, ListNode pHead2){
		
		if(pHead1 == null || pHead2 == null){
			return null;
		}
		
		int count1 = 0;
		ListNode p1 = pHead1;
		while(p1!=null){
			p1 = p1.next;
			count1 ++;
		}
		
		int count2 = 0;
		ListNode p2 = pHead2;
		while(p2!=null){
			p2 = p2.next;
			count2 ++;
		}
		
		int flag = count1 - count2;
		if(flag > 0){
			while(flag > 0){
				pHead1 = pHead1.next;
				flag --;
			}
			while(pHead1 != pHead2){
				pHead1 = pHead1.next;
				pHead2 = pHead2.next;
			}
			return pHead1;
		}
		
		if(flag < 0){
			while(flag < 0){
				pHead2 = pHead2.next;
				flag ++;
			}
			while(pHead1 != pHead2){
				pHead1 = pHead1.next;
				pHead2 = pHead2.next;
			}
			return pHead1;
		}
		return null;
	}
}

第四种解法

用两个指针，分别指向两个链表头部，同时往后走，当其中一个走到链表尾时，则令其指向另一个链表头。另一个链表也是如此，走到链表尾时，也指向另一个链表头。此时已满足领先要走步数要求。

①P1、P2分别指向pHead1、pHead2链表头部；

②P1、P2向后走m步，此时P1指向pHead1尾部；

③使P1指向pHead2头部；

④P2指向pHead2尾部；

⑤使P2指向pHead1头部，此时P2在pHead2中已走了m-n步。P1、P2继续向后走，直至找到公共结点，后续两链表长度均为m。

求两个链表的第一个公共节点

代码

/*
struct ListNode {
	int val;
	struct ListNode  next;
	ListNode(int x) {
		value = x;
	}
}*/
public class Solution {
	ListNode* FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
		ListNode  p1 = pHead1;
		ListNode  p2 = pHead2;
		while (p1  !=  p2)
		{
			//没有到链表尾部，则继续往后走  
			if (p1 != NULL)p1 = p1.next;
			if (p2 != NULL)p2 = p2.next;
			if (p1 != p2)
			{
				//若已到链表尾，则令其指向另一链表头  
				if (p1 == NULL) p1 = pHead2;
				if (p2 == NULL) p2 = pHead1;
			}
		}
		return p1;
	}
};

求两个链表的第一个公共节点

相关推荐