《剑指Offer》52：两个链表的第一个公共节点

题目

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

public static class ListNode{ public int val; public ListNode next; public ListNode(int val) { this.val = val; } }

分析

首先遍历两链表的长度。在第二次遍历的时候，在较长的链表上先走若干步，步数为两链表之差的绝对值，接着同时在两个链表遍历，找到的第一个相同的节点就是它们的第一个公共节点。

放码

public class FindTheSameNode { public ListNode find(ListNode head1, ListNode head2) { int length1 = count(head1); int length2 = count(head2); int diff = Math.abs(length1 - length2); ListNode pLong = length1 > length2 ? head1 : head2, pShort = length1 > length2 ? head2 : head1; while(diff > 0) { pLong = pLong.next; diff--; } while(pLong != null && pShort != null && pLong != pShort) { pLong = pLong.next; pShort = pShort.next; } return pLong == pShort ? pLong : null; } public int count(ListNode head) { int result = 0; ListNode p = head; while(p != null) { result++; p = p.next; } return result; } }

测试

import static org.junit.Assert.*; import org.junit.Test; import com.lun.util.SinglyLinkedList.ListNode; public class FindTheSameNodeTest { private static ListNode list1; private static ListNode list2; private static ListNode same; static { same = new ListNode(6); same.next = new ListNode(7); list1 = new ListNode(1); list1.next = new ListNode(2); list1.next.next = new ListNode(3); list1.next.next.next = same; list2 = new ListNode(4); list2.next = new ListNode(5); list2.next.next = same; } @Test public void testFind() { FindTheSameNode fn = new FindTheSameNode(); assertEquals(6, fn.find(list1, list2).val); assertEquals(same, fn.find(list1, list2)); } @Test public void testCount() { FindTheSameNode fn = new FindTheSameNode(); assertEquals(5, fn.count(list1)); assertEquals(4, fn.count(list2)); } }