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

た入场券 2022-12-11 15:27 102阅读 0赞

## 题目 ##

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

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));
    	}
    
    }