两个链表的第一个公共结点【Java版】
两个链表的第一个公共结点
http://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46
方法一:朴素对齐法(并列最优)
//本题朴素方法:代码虽长,但易读易懂、效率也同样高 public class Solution { public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { if(pHead1 == null || pHead2 == null)return null;//写完之后发现此方法可以省略判空 int len1 = 0; int len2 = 0; ListNode p1=pHead1;//测长度 ListNode p2=pHead2; while(p1 != null){ ++len1; p1=p1.next; } while(p2 != null){ ++len2; p2=p2.next; } p1=pHead1;//重新初始化 p2=pHead2; if(len1 > len2){ for(int i=0; i<len1-len2; ++i)p1=p1.next;//长的先跑diff,用于对齐 } if(len1 < len2){ for(int i=0; i<len2-len1; ++i)p2=p2.next; } while(p1 != p2){ p1=p1.next; p2=p2.next; } return p1; } } //时间复杂度:遍历2*(m+n)-2*common个节点 //时间O(m+n) //空间O(1)
方法二:双指针法(性能一致,优点是短)
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.next; p2=p2.next; if(p1 == null && p2 ==null)return null; if(p1 == null)p1 = pHead2;//这两行是关键:如果到头了,就从另一个的开头“复活” if(p2 == null)p2 = pHead1; } return p1; } } //时间复杂度:遍历2*(m+n)-2*common个节点 //时间O(m+n) //空间O(1)
《剑指Offer-Java题解》 文章被收录于专栏
《剑指Offer-Java题解》