题目描述
输入两个链表, 找出它们的第一个公共结点.
我的思路: 因为是链表, 长度都是未知的, 不能盲目的两个一起开始自增判断.
首先需要得到 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;
- }
- }
来源: http://www.bubuko.com/infodetail-2863956.html