架构师训练营-第八周练习：作业

[rooobot]

问题：

有两个单向链表（链表长度分别是m和n），这两个单向链表有可能在某个元素合并，如下图所示的这样，也可能不合并。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的x元素。

请用（伪）代码描述算法，并给出时间复杂度和空间复杂度。

[rooobot]

问题分析

算法的输入是两个单链表（只有head元素，同时，这里需要知道两个链表的长度值）。

合并：从某个节点开始往后，两个链表的所有元素值都相等（这里隐含着合并的情况下，重合的元素长度一致，同时也意味着从第一个相等的元素开始，两个单向链表后面的元素个数是相等的）。

算法设计：

两个单向链表的长度存在三种可能：m > n、m == n和m < n。

对于长度不相等的情况，按照上面的分析（从第一个相等的元素开始，两个单向链表后面的元素个数相等），我们需要先将长的单向链表向前走|m -n|（m与n的差的绝对值）步，然后比较后面相同长度的部分是否会出现合并的情况。

对于长度相等的情况，可以直接进行判断的逻辑。

对于整个判断，我们只需要一次遍历即可判断完成。

[rooobot]

代码实现

首先是算法的实现代码，其中LinkNode是链表的节点，LinkNodeList是一个辅助类，主要是问题中涉及到单向链表的长度，同时辅助单向链表的构建。

/**
 * @author zhaoyang on 2020-07-27.
 */
public class MergedLinkList {

    /**
     * 单向链表的节点
     */
    public static class LinkNode {

        // 当前节点的值
        public String val;
        // 指向下一个节点
        public LinkNode next;

        public LinkNode(String val) {
            this.val = val;
        }
    }

    /**
     * 单向链表List，主要是用来辅助初始化单向链表，同时记录链表的长度
     */
    public static class LinkNodeList {

        private LinkNode head;
        private int size;

        public LinkNodeList() {
            head = null;
            size = 0;
        }

        public void addNode(LinkNode node) {
            assert node != null;
            LinkNode tmpNode = head;
            while (tmpNode != null && tmpNode.next != null) {
                tmpNode = tmpNode.next;
            }
            if (tmpNode == null) {
                head = node;
            } else {
                tmpNode.next = node;
            }
            size++;
        }

        public int size() {
            return size;
        }
    }

    // 出现合并时的节点（第一个相等的节点）
    private LinkNode firstMergedNode = null;

    /**
     * 返回合并时的节点的值
     * @return val
     */
    public String mergedVal() {
        return firstMergedNode == null ? null : firstMergedNode.val;
    }

    /**
     * 判断两个单向链表是否是合并的
     * @param mList 长度为 m 的单向链表
     * @param nList 长度为 n 的单向链表
     * @return boolean 两个单向链表是否合并的，true表示是合并的，false表示不是合并的
     */
    public boolean isMerged(LinkNodeList mList, LinkNodeList nList) {
        assert mList.size() != 0;
        assert nList.size() != 0;

        int mSize = mList.size();
        int nSize = nList.size();

        int diffSize = 0;
        boolean isMerged = false;
        // 判断两个链表长度的差值，根据不同的情况来分别处理
        // 实际判断时只需要传入链表的头节点
        // m > n的情况
        if (mSize > nSize) {
            diffSize = mSize - nSize;
            // mList 先向前走 diffSize 步
            LinkNode forwarded = forward(diffSize, mList.head);
            // 判断后面等长的部分是否出现合并
            isMerged = validate(forwarded, nList.head, nSize);
        } else if (mSize < nSize) { // m < n 的情况
            diffSize = nSize - mSize;
            LinkNode forwarded = forward(diffSize, nList.head);
            isMerged = validate(mList.head, forwarded, nSize);
        } else {    // m == n 的情况
            isMerged = validate(mList.head, nList.head, mSize);
        }

        return isMerged;
    }

    /**
     * 将单向链表 inNode 向前走 diffSize 步
     * @param diffSize 需要向前走的步数
     * @param headNode 需要向前走的链表头节点
     * @return LinkNode 向前走 diffSize 步之后的节点
     */
    private LinkNode forward(int diffSize, LinkNode headNode) {
        assert diffSize > 0;
        LinkNode node = headNode;
        while (--diffSize >= 0) {
            if (node.next == null) {
                break;
            } else {
                node = node.next;
            }
        }
        return node;
    }

    /**
     * 判断两个等长（长度为 size）的链表是否是合并的
     * @param mNode 要判断的单向链表 mNode
     * @param nNode 要判断的单向链表 nNode
     * @param size 链表的长度
     * @return boolean 两个单向链表是否是合并的
     */
    private boolean validate(LinkNode mNode, LinkNode nNode, int size) {
        boolean isMerged = false;

        LinkNode mTmpNode = mNode;
        LinkNode nTmpNode = nNode;
        while (--size >= 0) {
            // 到了单向链表的尾部，跳出循环
            if (mTmpNode.next == null || nTmpNode == null) {
                break;
            }
            // 如果没有相等过，则一相等就赋值为 true
            if (!isMerged) {
                if (mTmpNode.val.equals(nTmpNode.val)) {
                    isMerged = true;
                    firstMergedNode = mTmpNode;
                }
                mTmpNode = mTmpNode.next;
                nTmpNode = nTmpNode.next;
            } else {
                // 如果已经是 true，则必须一直 true，只要一 false，马上返回
                if (!mTmpNode.val.equals(nTmpNode.val)) {
                    return false;
                }
            }
        }

        return isMerged;
    }

}

下面是测试用例：

import org.junit.Test;

import java.util.Arrays;
import java.util.List;

import static org.junit.Assert.*;

/**
 * @author zhaoyang on 2020-07-27.
 */
public class TestMergedLinkList {

    public MergedLinkList.LinkNodeList build(List<String> list) {
        MergedLinkList.LinkNodeList nodeList = new MergedLinkList.LinkNodeList();
        list.forEach(x -> nodeList.addNode(new MergedLinkList.LinkNode(x)));
        return nodeList;
    }

    @Test
    public void Test_MLengthLessThanNLength_CanMerged1() {
        MergedLinkList.LinkNodeList mList = build(Arrays.asList("a", "b", "x", "y", "z"));
        MergedLinkList.LinkNodeList nList = build(Arrays.asList("d", "e", "f", "x", "y", "z"));
        MergedLinkList mergedLinkList = new MergedLinkList();
        boolean isMerged = mergedLinkList.isMerged(mList, nList);
        assertTrue("should be true", isMerged);
        String mergedVal = mergedLinkList.mergedVal();
        assertEquals("merged val should be x", mergedVal, "x");
    }

    @Test
    public void Test_MLengthEqualsNLength_CanMerged2() {
        MergedLinkList.LinkNodeList mList = build(Arrays.asList("*", "a", "b", "x", "y", "z"));
        MergedLinkList.LinkNodeList nList = build(Arrays.asList("d", "e", "f", "x", "y", "z"));
        MergedLinkList mergedLinkList = new MergedLinkList();
        boolean isMerged = mergedLinkList.isMerged(mList, nList);
        assertTrue("should be true", isMerged);
        String mergedVal = mergedLinkList.mergedVal();
        assertEquals("merged val should be x", mergedVal, "x");
    }

    @Test
    public void Test_MLengthEqualsNLength_CanMerged3() {
        MergedLinkList.LinkNodeList mList = build(Arrays.asList("d", "e", "f", "x", "y", "z"));
        MergedLinkList.LinkNodeList nList = build(Arrays.asList("d", "e", "f", "x", "y", "z"));
        MergedLinkList mergedLinkList = new MergedLinkList();
        boolean isMerged = mergedLinkList.isMerged(mList, nList);
        assertTrue("should be true", isMerged);
        String mergedVal = mergedLinkList.mergedVal();
        assertEquals("merged val should be d", mergedVal, "d");
    }

    @Test
    public void Test_MLengthLargerThanNLength_CanMerged4() {
        MergedLinkList.LinkNodeList mList = build(Arrays.asList("*", "&", "a", "b", "x", "y", "z"));
        MergedLinkList.LinkNodeList nList = build(Arrays.asList("d", "e", "f", "x", "y", "z"));
        MergedLinkList mergedLinkList = new MergedLinkList();
        boolean isMerged = mergedLinkList.isMerged(mList, nList);
        assertTrue("should be true", isMerged);
        String mergedVal = mergedLinkList.mergedVal();
        assertEquals("merged val should be x", mergedVal, "x");
    }

    @Test
    public void Test_MLengthEqualsNLength_CanNotMerged1() {
        MergedLinkList.LinkNodeList mList = build(Arrays.asList("a", "b", "x", "y", "z", "*"));
        MergedLinkList.LinkNodeList nList = build(Arrays.asList("d", "e", "f", "x", "y", "z"));
        MergedLinkList mergedLinkList = new MergedLinkList();
        boolean isMerged = mergedLinkList.isMerged(mList, nList);
        assertFalse("should not be true", isMerged);
    }

    @Test
    public void Test_MLengthLessThanNLength_CanNotMerged2() {
        MergedLinkList.LinkNodeList mList = build(Arrays.asList("a", "b", "x", "y", "z"));
        MergedLinkList.LinkNodeList nList = build(Arrays.asList("d", "e", "f", "x", "y", "z", "*"));
        MergedLinkList mergedLinkList = new MergedLinkList();
        boolean isMerged = mergedLinkList.isMerged(mList, nList);
        assertFalse("should not be true", isMerged);
    }

    @Test
    public void Test_MLengthEqualsNLength_CanNotMerged3() {
        MergedLinkList.LinkNodeList mList = build(Arrays.asList("a", "b", "c", "d", "e", "f"));
        MergedLinkList.LinkNodeList nList = build(Arrays.asList("g", "h", "i", "j", "k", "k"));
        MergedLinkList mergedLinkList = new MergedLinkList();
        boolean isMerged = mergedLinkList.isMerged(mList, nList);
        assertFalse("should not be true", isMerged);
    }

    @Test
    public void TestMLengthLargerThanNLength_CanNotMerged4() {
        MergedLinkList.LinkNodeList mList = build(Arrays.asList("g", "h", "i", "j", "k", "k", "*"));
        MergedLinkList.LinkNodeList nList = build(Arrays.asList("a", "b", "c", "d", "e", "f"));
        MergedLinkList mergedLinkList = new MergedLinkList();
        boolean isMerged = mergedLinkList.isMerged(mList, nList);
        assertFalse("should not be true", isMerged);
    }

}

测试用例的执行结果：

Testing started at 11:09 上午 ...
> Task :cleanTest
> Task :compileJava
> Task :processResources UP-TO-DATE
> Task :classes
> Task :compileTestJava
> Task :processTestResources NO-SOURCE
> Task :testClasses
> Task :test
me.zy.algorithm.TestMergedLinkList > Test_MLengthLargerThanNLength_CanMerged4 PASSED
me.zy.algorithm.TestMergedLinkList > Test_MLengthEqualsNLength_CanMerged2 PASSED
me.zy.algorithm.TestMergedLinkList > Test_MLengthEqualsNLength_CanMerged3 PASSED
me.zy.algorithm.TestMergedLinkList > Test_MLengthLessThanNLength_CanMerged1 PASSED
me.zy.algorithm.TestMergedLinkList > Test_MLengthLessThanNLength_CanNotMerged2 PASSED
me.zy.algorithm.TestMergedLinkList > TestMLengthLargerThanNLength_CanNotMerged4 PASSED
me.zy.algorithm.TestMergedLinkList > Test_MLengthEqualsNLength_CanNotMerged1 PASSED
me.zy.algorithm.TestMergedLinkList > Test_MLengthEqualsNLength_CanNotMerged3 PASSED
BUILD SUCCESSFUL in 1s
5 actionable tasks: 4 executed, 1 up-to-date
11:09:28 上午: Tasks execution finished ':cleanTest :test --tests "me.zy.algorithm.TestMergedLinkList"'.

测试用例全部通过。

[rooobot]

时间复杂度与空间复杂度

在算法的实现中，对于输入的两个单向链表，都只遍历了一遍，所以，时间复杂度为O(max(m,n))，也就是O(n)。

在算法的实现过程中，并没有额外的开辟内存空间，最后要返回的元素值是存在单个节点对象中的，所以空间复杂度为O(1)。

即上面的算法实现，时间复杂度为O(n)，空间复杂度为O(1)。