使用双指针 找出两个链表的第一个公共节点
两个链表的第一个公共结点
http://www.nowcoder.com/questionTerminal/6ab1d9a29e88450685099d45c9e31e46
分析:
公共节点之后的节点都是相同的,或者说公共节点之后的部分都是相同的,所以要返回第一个公共节点,让两个链表同时走,短的走完走长的,长的走完走短的,那么一定可以遇到公共节点:
情况1、长度相同:
1.1有公共节点,那么公共节点后面是相同的,所以节点位置一定相同,两个链表齐头并进一定可以找到;
1.2无公共节点,那么一起走到最后都是null,也可以返回null
情况2、长度不同:
2.1有公共节点,那么单程短的先走完接着走长的,长的走完接着走短的,长+短 = 短+长,两路最后还是一样的,从后往前看公共节点后面部分相同,一定能碰到公共节点;
2.2无公共节点,那么长+短 和 短+长两路最后没有公共部分,但是最终长度相等,共同走到null
/* 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 p1 = pHead1; ListNode p2 = pHead2; while(p1 != p2){ p1 = (p1 == null ? pHead2 : p1.next); p2 = (p2 == null ? pHead1 : p2.next); } return p1; } }