Java找出两个链表的第一个公共节点

题目描述

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

我的思路：因为是链表，长度都是未知的，不能盲目的两个一起开始自增判断。

首先需要得到 L1的长度 和 L2的长度，让较长的那个先走 （length1-length2）步。然后再一直next去判断。

AC代码， 34ms,503K

/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Solution { public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { if(pHead1==pHead2){ return pHead1; } int l1=getLength(pHead1); int l2=getLength(pHead2); if(l1>l2){ for(int i=0;i<(l1-l2);i++){ pHead1=pHead1.next; } }else{ for(int i=0;i<(l1-l2);i++){ pHead2=pHead2.next; } } boolean f=true; ListNode p=null; while(f){ if(pHead1==null||pHead2==null){ return null; } if(pHead1==pHead2){ p=pHead1; f=false; }else{ pHead1=pHead1.next; pHead2=pHead2.next; } } return p; } public static int getLength(ListNode pHead) {         int length = 0;           ListNode current = pHead;         while (current != null) {             length++;             current = current.next;         }         return length;     } }

看看别的思路：

1、用HashMap: 

第一个while是把pHead1的所有节点都放进去。

第二个while开始，对pHead2的每个节点都用  containsKey 方法来判断。 

因为在前一种思路中，要求得两个链表的长度就需要对两个链表进行一次遍历，用HashMap的方法其实更加节省时间。

33ms,503K

import java.util.*; /* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Solution {     public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {         ListNode current1 = pHead1;         ListNode current2 = pHead2;             HashMap<ListNode, Integer> hashMap = new HashMap<ListNode, Integer>();         while (current1 != null) {             hashMap.put(current1, null);             current1 = current1.next;         }         while (current2 != null) {             if (hashMap.containsKey(current2))                 return current2;             current2 = current2.next;         }           return null;       } }