题目描述 输入两个链表，找出它们的第一个公共结点。
题目解析 如果两个链表有公共结点，那么两个链表公共结点之后的结点也都相同，那么两个链表交叉后一定是一个Y型，所以如果我们将两个链表放到两个栈里边，当我们从栈里边同时出栈两个链表的结点，直到最后一个相同的结点，这是算法1。对于两个不同的链表，有公共结点的话，那么如果我们先遍历一个较长的链表，让两个链表剩下的结点个数相同，那么我们只需要同时遍历两个链表，直到第一个相同的结点。
代码如下：
public static ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { if (pHead1 == null || pHead2 == null) { return null; } Stack<ListNode> stack1 = new Stack<>(); Stack<ListNode> stack2 = new Stack<>(); ListNode temp = pHead1; while (temp != null) { stack1.push(temp); temp = temp.next; } temp = pHead2; while (temp != null) { stack2.push(temp); temp = temp.next; } temp = null; ListNode node1 = null; ListNode node2 = null; while (stack1.size() > 0 && stack2.size() > 0){ node1 = stack1.pop(); node2 = stack2.pop(); if (node1.val == node2.val && node1.next == node2.next){ temp = node1; }else{ break; } } return temp; } public ListNode FindFirstCommonNode2(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){ pHead2 = pHead2.next; pHead1 = pHead1.next; } return pHead1; } return null; }新闻热点
疑难解答
