本系列導(dǎo)航：劍指offer（第二版）java實(shí)現(xiàn)導(dǎo)航帖

面試題52：兩個(gè)鏈表的第一個(gè)公共節(jié)點(diǎn)

題目要求：
輸入兩個(gè)單鏈表，找出它們的第一個(gè)公共節(jié)點(diǎn)。以下圖為例镜会，對(duì)一個(gè)公共節(jié)點(diǎn)為6所在的節(jié)點(diǎn)。

1 -> 2 -> 3 -> 6 -> 7
     4 -> 5 ↗

解題思路：

解法1：比較直接，不再贅述著隆。

解法2：從鏈表的尾部向前看扰楼，發(fā)現(xiàn)尾部是相同的，向前走會(huì)分叉美浦，找到分叉點(diǎn)即可弦赖。按照這個(gè)思路，如果這是雙向鏈表浦辨，即得到尾節(jié)點(diǎn)并能夠得到每個(gè)節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)蹬竖，那這個(gè)題就很簡(jiǎn)單了。對(duì)于單鏈表，本身是前節(jié)點(diǎn)->后節(jié)點(diǎn)币厕，想要得到后節(jié)點(diǎn)->前節(jié)點(diǎn)列另，可以借助于棧的后進(jìn)先出特性。兩個(gè)單鏈表分別入棧旦装，得到[1,2,3,6,7],[4,5,6,7]页衙，然后不斷出棧即可找到分叉點(diǎn)。

解法3：對(duì)于單鏈表阴绢，如果從頭結(jié)點(diǎn)開(kāi)始找公共節(jié)點(diǎn)店乐，一個(gè)麻煩點(diǎn)是兩個(gè)鏈表長(zhǎng)度可能不一致，因此兩個(gè)指針不同步（指兩個(gè)指針無(wú)法同時(shí)指向公共點(diǎn)）呻袭。解決這個(gè)麻煩點(diǎn)响巢，整個(gè)問(wèn)題也就能順利解決。那么棒妨，能否讓兩個(gè)鏈表長(zhǎng)度一致踪古？長(zhǎng)鏈表先行幾步即可，因?yàn)殚L(zhǎng)鏈表頭部多出的那幾個(gè)節(jié)點(diǎn)一定不會(huì)是兩鏈表的公共節(jié)點(diǎn)券腔。以題目中的圖為例伏穆，可以讓1所在的鏈表先向前移動(dòng)1個(gè)節(jié)點(diǎn)到2，這樣就轉(zhuǎn)化為求下面這兩個(gè)鏈表的第一個(gè)公共節(jié)點(diǎn)：

2 -> 3 -> 6 -> 7
4 -> 5 ↗

一個(gè)指針指向2纷纫，另一個(gè)指向4枕扫，然后同時(shí)遍歷，這應(yīng)該很容易了吧辱魁。需要對(duì)兩個(gè)鏈表先進(jìn)行一次遍歷求出長(zhǎng)度烟瞧，然后再同時(shí)遍歷求公共點(diǎn)，時(shí)間復(fù)雜度o(n)染簇，空間復(fù)雜度o(1)参滴。

三種解法的代碼實(shí)現(xiàn)如下。

package chapter5;
import structure.ListNode;

import java.util.Stack;

/**
 * Created with IntelliJ IDEA
 * Author: ryder
 * Date  : 2017/8/15
 * Time  : 10:28
 * Description:兩個(gè)鏈表的第一個(gè)公共節(jié)點(diǎn)
 **/
public class P253_CommonNodesInLists {
    //思路一：暴力解決锻弓，時(shí)間復(fù)雜度o(mn)砾赔，空間復(fù)雜度o(1)
    //思路二：借助于兩個(gè)棧，時(shí)間復(fù)雜度o(m+n)青灼，空間復(fù)雜度o(m+n)
    //思路三：轉(zhuǎn)化為等長(zhǎng)鏈表暴心，時(shí)間復(fù)雜度o(m+n)，空間復(fù)雜度o(1)
    public static ListNode<Integer> findFirstCommonNode(ListNode<Integer> head1,ListNode<Integer> head2){
        for(ListNode<Integer> node1=head1;node1!=null;node1=node1.next){
            for(ListNode<Integer> node2=head2;node2!=null;node2=node2.next){
                if(node1==node2)
                    return node1;
            }
        }
        return null;
    }
    public static ListNode<Integer> findFirstCommonNode2(ListNode<Integer> head1,ListNode<Integer> head2){
        Stack<ListNode<Integer>> stack1 = new Stack<>();
        Stack<ListNode<Integer>> stack2 = new Stack<>();
        for(ListNode<Integer> node1=head1;node1!=null;node1=node1.next)
            stack1.push(node1);
        for(ListNode<Integer> node2=head2;node2!=null;node2=node2.next)
            stack2.push(node2);
        ListNode<Integer> commonNode = null;
        while (!stack1.isEmpty() && !stack2.isEmpty()){
            if(stack1.peek()==stack2.peek()){
                commonNode = stack1.pop();
                stack2.pop();
            }
            else
                break;
        }
        return commonNode;
    }
    public static ListNode<Integer> findFirstCommonNode3(ListNode<Integer> head1,ListNode<Integer> head2){
        ListNode<Integer> node1 = head1,node2 = head2;
        int size1 = 0,size2 = 0;
        for (;node1!=null;node1 = node1.next)
            size1++;
        for (;node2!=null;node2 = node2.next)
            size2++;
        node1 = head1;
        node2 = head2;
        while (size1>size2){
            node1 = node1.next;
            size1--;
        }
        while (size2>size1){
            node2 = node2.next;
            size2--;
        }
        while (node1!=null){
            if(node1!=node2){
                node1 = node1.next;
                node2 = node2.next;
            }
            else
                break;
        }
        return node1;
    }
    public static void main(String[] args){
        // 1->2->3->6->7
        //    4->5↗
        ListNode<Integer> node1 = new ListNode<>(1);
        ListNode<Integer> node2 = new ListNode<>(2);
        ListNode<Integer> node3 = new ListNode<>(3);
        ListNode<Integer> node4 = new ListNode<>(4);
        ListNode<Integer> node5 = new ListNode<>(5);
        ListNode<Integer> node6 = new ListNode<>(6);
        ListNode<Integer> node7 = new ListNode<>(7);
        node1.next = node2;
        node2.next = node3;
        node3.next = node6;
        node4.next = node5;
        node5.next = node6;
        node6.next = node7;
        ListNode<Integer> commonNode = findFirstCommonNode(node1,node4);
        System.out.println(commonNode.val);
        ListNode<Integer> commonNode2 = findFirstCommonNode2(node1,node4);
        System.out.println(commonNode2.val);
        ListNode<Integer> commonNode3 = findFirstCommonNode2(node1,node4);
        System.out.println(commonNode3.val);
    }
}

運(yùn)行結(jié)果

6
6
6