剑指offer-问题37

一时失言乱红尘 2022-05-11 15:16 144阅读 0赞

package offer;
    
    /**
     * offer interview 37
     */
    public class Test37 {
        private static class ListNode{
            int val;
            ListNode next;
    
            public ListNode(){}
            public ListNode(int val){
                this.val = val;
            }
    
            @Override
            public String toString(){
                return val + "";
            }
        }
    
        public static ListNode findFirstCommonNode(ListNode head1 , ListNode head2){
            int length1 = getListLength(head1);
            int length2 = getListLength(head2);
    
            int diff = length1 - length2;
            ListNode longListHead = head1;
            ListNode shortListHead = head2;
    
            if (diff < 0){
                longListHead = head2;
                shortListHead = head1;
                diff = length2 - length1;
            }
    
            for (int i = 0 ; i < diff; i++){
                longListHead = longListHead.next;
            }
    
            while (longListHead != null
                    && shortListHead != null
                    && longListHead != shortListHead){
                longListHead = longListHead.next;
                shortListHead = shortListHead.next;
            }
    
            return longListHead;
        }
    
        private static int getListLength(ListNode head){
            int result = 0;
            while (head != null){
                result++;
                head = head.next;
            }
            return result;
        }
    
    
        private static void test1(){
            // 第一个公共结点在链表中间
            // 1 - 2 - 3 \
            //            6 - 7
            //     4 - 5 /
            ListNode n1 = new ListNode(1);
            ListNode n2 = new ListNode(2);
            ListNode n3 = new ListNode(3);
            ListNode n6 = new ListNode(6);
            ListNode n7 = new ListNode(7);
    
            ListNode n4 = new ListNode(4);
            ListNode n5 = new ListNode(5);
    
            n1.next = n2;
            n2.next = n3;
            n3.next = n6;
            n6.next = n7;
    
            n4.next = n5;
            n5.next = n6;
    
            System.out.println(findFirstCommonNode(n1,n4));
    
        }
    
    
        private static void test2() {
            // 没有公共结点
            // 1 - 2 - 3 - 4
            //
            // 5 - 6 - 7
            ListNode n1 = new ListNode(1);
            ListNode n2 = new ListNode(2);
            ListNode n3 = new ListNode(3);
            ListNode n4 = new ListNode(4);
            ListNode n5 = new ListNode(5);
            ListNode n6 = new ListNode(6);
            ListNode n7 = new ListNode(7);
    
            n1.next = n2;
            n2.next = n3;
            n3.next = n4;
    
            n5.next = n6;
            n6.next = n7;
            System.out.println(findFirstCommonNode(n1, n5)); // null
        }
    
        private static void test3() {
            // 公共结点是最后一个结点
            // 1 - 2 - 3 - 4 \
            //                7
            //         5 - 6 /
            ListNode n1 = new ListNode(1);
            ListNode n2 = new ListNode(2);
            ListNode n3 = new ListNode(3);
            ListNode n4 = new ListNode(4);
            ListNode n5 = new ListNode(5);
            ListNode n6 = new ListNode(6);
            ListNode n7 = new ListNode(7);
    
            n1.next = n2;
            n2.next = n3;
            n3.next = n4;
            n4.next = n7;
    
            n5.next = n6;
            n6.next = n7;
            System.out.println(findFirstCommonNode(n1, n5)); // 7
        }
    
        private static void test4() {
            // 公共结点是第一个结点
            // 1 - 2 - 3 - 4 - 5
            // 两个链表完全重合
            ListNode n1 = new ListNode(1);
            ListNode n2 = new ListNode(2);
            ListNode n3 = new ListNode(3);
            ListNode n4 = new ListNode(4);
            ListNode n5 = new ListNode(5);
            ListNode n6 = new ListNode(6);
            ListNode n7 = new ListNode(7);
    
            n1.next = n2;
            n2.next = n3;
            n3.next = n4;
            n4.next = n5;
    
            System.out.println(findFirstCommonNode(n1, n1)); // 1
        }
    
        public static void main(String[] args){
            test1();
            test2();
            test3();
            test4();
        }
    
    
    
    }

====

欢迎加入群聊：

![70][]

[70]: /images/20220505/edc55c937a1d427aa7852be8b30769fd.png