剑指Offer-两个链表的第一个公共结点

r囧r小猫 2022-02-19 05:21 178阅读 0赞

## 题目描述 ##

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

解题思路—**长度长的链表先走**：**看完题目首先要明确一点，如果链表中存在公共结点，则链表尾一定是一样的！** 所以可以先找出2个链表的长度，然后让**长的先走**两个链表的**长度差**，然后再一起走。

解题思路—**链表循环**：这个方法非常的**巧妙**！**不需要考虑链表的长度**！**用两个指针扫描两个链表，最终两个指针到达 null 或者到达公共结点**。**推荐**！

核心思想为：
    长度相同有公共结点，第一次就能遍历到；没有公共结点，走到尾部NULL相遇，返回NULL；
    长度不同有公共结点，第一遍遍历出差值，第二遍一起到公共结点；没有公共结点，则一起到结尾，返回NULL。

解题思路—**HashMap**：可以使用HashMap的特点，先将一个链表存入HashMap，再**依次判断另一个链表的结点是否存在于HashMap中**。  
解题思路—**堆栈**：这个方法的着手点为两个链表要是有公共结点，**必有公共链表尾**。使用堆栈将链表压入，**从尾部开始判断，直至链表结点不相等**。

## Java解题—长度长的链表先走 ##

public class Solution {
        public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
            ListNode current1 = pHead1;
            ListNode current2 = pHead2;
            if (pHead1 == null || pHead2 == null)
                return null;
            int length1 = getLength(current1);
            int length2 = getLength(current2);
             
            // 链表1.length>链表2.length，链表1先走
            if (length1 >= length2) {
                int len = length1 - length2;
                while (len > 0) {
                    current1 = current1.next;
                    len--;
                }
     
            }
            // 链表2.length>链表1.length，链表2先走
            else if (length1 < length2) {
                int len = length2 - length1;
                while (len > 0) {
                    current2 = current2.next;
                    len--;
                }
            }
            
            //两个链表一起走
            while(current1!=current2){
                current1=current1.next;
                current2=current2.next;
            }
            return current1;
        }
        
        public int getLength(ListNode pHead) {
            int length = 0;
     
            ListNode current = pHead;
            while (current != null) {
                length++;
                current = current.next;
            }
            return length;
        }
    }

## Java解题—链表循环 ##

public class Solution {
        public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        	if (pHead1 == null || pHead2 == null)
                return null;
            ListNode p1 = pHead1;
            ListNode p2 = pHead2;
            
            while(p1!=p2){
                p1 = (p1==null ? pHead2: p1.next);
                p2 = (p2==null ? pHead1: p2.next);
            }
            
            return p1;
        }
    }

## Java解题—HashMap ##

import java.util.HashMap;
    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;
        }
    }

## Java解题—堆栈 ##

import java.util.Stack;
    public class Solution {
        public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        	if (pHead1 == null || pHead2 == null) 
                return null;
            
            Stack<ListNode> stack1 = new Stack<>();
            Stack<ListNode> stack2 = new Stack<>();
     
            while (pHead1 != null) {
                stack1.push(pHead1);
                pHead1 = pHead1.next;
            }
     
            while (pHead2 != null) {
                stack2.push(pHead2);
                pHead2 = pHead2.next;
            }
     
            ListNode commonListNode = null;
     
            while (!stack1.isEmpty() && !stack2.isEmpty() && stack1.peek() == stack2.peek() ) {
                stack2.pop();
                commonListNode = stack1.pop();;
            }
     
            return commonListNode;
        }
    }