【剑指offer-Java版】37两个链表的第一个公共结点

梦里梦外; 2022-08-21 09:48 93阅读 0赞

两个链表中的第一个公共顶点：  
解法一：两次遍历即可  
第一次遍历找到两个链表的长度，求出差值k，然后较长的；链表先走k步，之后两个链表同时走，直到遇到第一个相同的结点为止

解法二：辅助栈，先顺序遍历并将链表内容存储到栈中，然后依次弹栈，直到遇到最后一个不同结点

public class _Q37<T> {
    
        public ListNode<T> FindFirstCommonNode(ListNode<T> list1, ListNode<T> list2){
            if(list1 == null || list2 == null) return null;
    
            ListNode<T> node1 = list1;
            ListNode<T> node2 = list2;
    
            int len1 = 0;
            int len2 = 0;
            while(node1 != null) {node1 = node1.next; len1++;}
            while(node2 != null) {node2 = node2.next; len2++;}
    
            node1 = list1;
            node2 = list2;
            int k = 0;
            if(len1 >= len2){
                k = len1 - len2;
                while(k > 0){ node1 = node1.next; --k;}
            }else{
                k = len2 - len1;
                while(k > 0){ node2 = node2.next; --k;}
            }
    
            while (node1 != null && node2 != null && node1.value != node2.value) {
                node1 = node1.next;
                node2 = node2.next;
            }
    
            return node1; // node可能为空，因为可能输入链表中并没有相同结点
        }
        }

测试代码：

public class _Q37Test extends TestCase {
        
    
        _Q37<Integer> firstCommon = new _Q37<Integer>();
    
        public void test(){
            // 一旦第一个相同，后面都必须相同
            int array1[] = {
       1, 2, 3, 4, 5, 6};
            int array2[] = {
       6};
            int array3[] = {
       7, 8, 9, 10};
            ListNode<Integer> list1 = new ListNode<Integer>();
            ListNode<Integer> list2 = new ListNode<Integer>();
            ListNode<Integer> list3 = new ListNode<Integer>();
    
            ListNode<Integer> p = list1;
            for(int i=0; i<array1.length; i++){
                ListNode<Integer> node = new ListNode<>();
                node.value = array1[i];
                node.next = p.next;
                p.next = node;
                p = p.next;
            }
    
            p = list2;
            for(int i=0; i<array2.length; i++){
                ListNode<Integer> node = new ListNode<>();
                node.value = array2[i];
                node.next = p.next;
                p.next = node;
                p = p.next;
            }
    
            p = list3;
            for(int i=0; i<array2.length; i++){
                ListNode<Integer> node = new ListNode<>();
                node.value = array3[i];
                node.next = p.next;
                p.next = node;
                p = p.next;
            }
    
            System.out.println(firstCommon.FindFirstCommonNode(list1.next, list2.next).value);
            if(firstCommon.FindFirstCommonNode(list1.next, list3.next) != null){
                System.out.println(firstCommon.FindFirstCommonNode(list1.next, list3.next).value);
            }else{
                System.out.println("null");
            }
        }
        }