架构师训练营第八周作业

package org.geekbang.week8;
public class CommonLinkedList
{
    public static void main(String[] args)
    {
        Node a = new Node("a");
        Node b = new Node("b");
        Node d = new Node("d");
        Node e = new Node("e");
        Node f = new Node("f");
        Node x = new Node("x");
        Node y = new Node("y");
        Node z = new Node("z");
        a.next(b);
        b.next(x);
        x.next(y);
        y.next(z);
        d.next(e);
        e.next(f);
        f.next(x);
        System.out.println("linkedlist1:");
        a.printList();
        System.out.println("linkedlist2:");
        d.printList();
        System.out.println("common list:");
        Node commonNode = getCommonNode(a, d);
        if (commonNode != null)
        {
            commonNode.printList();
        } else
        {
            System.out.println("no common node");
        }
    }
    /**
     * 判断list2是否是list1的尾链
     *
     * @param list1
     * @param list2
     * @return
     */
    public static boolean isTail(Node list1, Node list2)
    {
        if (list1 == null || list2 == null)
        {
            return false;
        }
        Node n1 = list1;
        Node n2 = list2;
        //在list1中找到list2的头结点
        while (n1 != n2 && n1 != null)
        {
            n1 = n1.next();
        }
        while (n1 != null && n2 != null)
        {
            if (n1 == n2)
            {
                n1 = n1.next();
                n2 = n2.next();
            } else
            {
                return false;
            }
        }
        //如果是尾链，此时两个指针都应该指向null
        if (n1 != null || n2 != null)
        {
            return false;
        } else
        {
            return true;
        }
    }
    public static Node getCommonNode(Node list1, Node list2)
    {
        int count1 = list1.count();
        int count2 = list2.count();
        Node n1 = null;
        Node n2 = null;
        if (count1 > count2)
        {
            n1 = list1;
            n2 = list2;
        } else
        {
            n1 = list2;
            n2 = list1;
        }
        while (!isTail(n1, n2))
        {
            n2 = n2.next();
        }
        return n2;
    }
}

package org.geekbang.week8;
public class Node<T>
{
    private T data;
    private Node<T> next;
    public Node(T data)
    {
        this.data = data;
    }
    public Node<T> next()
    {
        return next;
    }
    public void next(Node<T> next)
    {
        this.next = next;
    }
    @Override
    public String toString()
    {
        return data.toString();
    }
    public void printList()
    {
        System.out.print(this + " → ");
        Node curNode = this;
        while (curNode.next != null)
        {
            curNode = curNode.next;
            System.out.print(curNode + " → ");
        }
        System.out.println("null");
    }
    public int count()
    {
        int count = 1;
        Node curNode = this;
        while (curNode.next != null)
        {
            count++;
            curNode = curNode.next;
        }
        return count;
    }
}