宝鸡网站建设公司/百度关键词排名价格

题目描述

题目地址：两个链表的第一个公共节点

解法一：暴力枚举

一个朴素的想法是直接对每一个节点进行枚举，这样做的时间复杂度是O(M*N)。

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {for(ListNode pa = headA; pa!=null; pa = pa.next) {for(ListNode pb = headB; pb!=null; pb = pb.next) {if(pa==pb) {return pa;}}}return null;}
}

解法二：哈希集合

从一个头结点开始遍历一遍，将所有节点放入一个哈希集合中，再从另一个头结点开始遍历，遍历到第一个在哈希集合中的节点就是第一个相遇的节点。

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {Set<ListNode> set = new HashSet<ListNode>();ListNode temp = headA;while(temp!=null) {set.add(temp);temp = temp.next;}while(headB!=null) {if(set.contains(headB)) {return headB;}headB = headB.next;}return null;}
}

解法三：双指针

如果一开始两个指针都为空，直接返回空。
两个临时指针分别从两个头结点开始遍历，遍历到结尾后回到头结点继续往下，两个临时节点每一次共同更新一步，总有一天两个节点会相遇。

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode pa=headA, pb=headB;if(pa==null & pb==null) {return null;}while(pa!=pb) {pa = pa == null ? headA : pa.next;pb = pb == null ? headB : pb.next;}return pa;}
}

解法四：双栈

维护两个栈，将两个头结点遍历的元素分别加入两个栈中。然后开始同时出栈，直到同时出栈的元素不同，说明上一个出栈的元素是第一个公共节点。

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode pa=headA, pb=headB;Deque<ListNode> d1 = new ArrayDeque<ListNode>(), d2 = new ArrayDeque<ListNode>();while(pa!=null) {d1.add(pa);pa = pa.next;}while(pb!=null) {d2.add(pb);pb = pb.next;}ListNode ans = null;while(!d1.isEmpty() && !d2.isEmpty() && d1.peekLast()==d2.peekLast()) {ans = d1.pollLast();d2.pollLast();}return ans;}
}