架构师训练营 - 命题作业第 8 周

 关注
发布于: 2020 年 07 月 26 日
有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，如下图所示的这样，也可能不合并。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。
    请用（伪）代码描述算法，并给出时间复杂度和空间复杂度。
﻿
解答：
需求分析：
假设 m和n已知，且 m >= n
如果2个链表在x结点合并，则2个链表从x结点开始到结束的结点完全一致。
假设2个链表一定存在合并，n链接的第1个结点到x结点有P个结点，且x结点到结束结点有Q个结点
则我们可以知道： m >= n >= Q  P + Q = n   
那么算法遍历，应该从n链表的第一个结点开始，应该从m链表的第 (m - n) 个结点开始遍历，
然后每次都同时递进这2个链接，并对比所在结点是否相同。
由上述描述可知：
时间复杂度是 O(m)，空间复杂度是O(1)。
注意：如果一开始，不知道m和n的大小关系，则需要先 各遍历一遍2个链表，以便得到m和n这2个长度值，时间复杂度变成 O(2m)。
﻿
m和n未知时，代码如下
已提交到Github： https://github.com/youbl/study/tree/master/linkedlist-merge-find
单向链表类定义：
package cn.beinet;
public class LinkedList {
    private String data;
    private LinkedList nextNode;
    public LinkedList(String data) {
        this.data = data;
    }
    public String getData() {
        return data;
    }
    public void setData(String data) {
        this.data = data;
    }
    public LinkedList getNextNode() {
        return nextNode;
    }
    public void setNextNode(LinkedList nextNode) {
        this.nextNode = nextNode;
    }
}
﻿
测试主调类：
package cn.beinet;
public class Main {
    public static void main(String[] args) {
        // 数据初始化
        LinkedList listM = initListM();
        LinkedList listN = initListN();
        // 添加合并结点，注释这一句，可测试无合并场景
        appendSameNode(listM, listN);
        // 开始查找
        LinkedList mergeNode = findMergeNode(listM, listN);
        if (mergeNode == null)
            System.out.println("不存在合并结点");
        else
            System.out.println("2个链表合并于结点： " + mergeNode.getData());
    }
    /**
     * 查找2个单向链表的合并结点，无合并时，返回null
     *
     * @param listM 链表m
     * @param listN 链表n
     * @return
     */
    private static LinkedList findMergeNode(LinkedList listM, LinkedList listN) {
        int m = getLen(listM);
        int n = getLen(listN);
        // 交换，确保listM是较大的链表
        if (m < n) {
            LinkedList tmp = listM;
            listM = listN;
            listN = listM;
            int tmpNum = m;
            m = n;
            n = tmpNum;
        }
        System.out.println("链表m长度 " + m + ", 链表n长度 " + n);
        listM = jumpToSameNum(listM, m - n); // m链表先遍历，确保m链表剩下的结点数 跟n链表一致
        for (int i = 0; i < n; i++) {
            if (listM.equals(listN))
                return listM;
            listM = listM.getNextNode();
            listN = listN.getNextNode();
        }
        return null;
    }
    private static int getLen(LinkedList list) {
        int ret = 1;
        while (list.getNextNode() != null) {
            ret++;
            list = list.getNextNode();
        }
        return ret;
    }
    // 大的链表，先遍历掉前面的结点，以便跟小链表同步
    private static LinkedList jumpToSameNum(LinkedList list, int jumpNum) {
        for (int i = 0; i < jumpNum; i++)
            list = list.getNextNode();
        return list;
    }
    private static LinkedList initListM() {
        LinkedList head = new LinkedList("d");
        LinkedList node1 = new LinkedList("e");
        head.setNextNode(node1);
        LinkedList node2 = new LinkedList("f");
        node1.setNextNode(node2);
        return head;
    }
    private static LinkedList initListN() {
        LinkedList head = new LinkedList("a");
        LinkedList node = new LinkedList("b");
        head.setNextNode(node);
        return head;
    }
    // 添加相同结点
    private static void appendSameNode(LinkedList listM, LinkedList listN) {
        while (listM.getNextNode() != null)
            listM = listM.getNextNode();
        while (listN.getNextNode() != null)
            listN = listN.getNextNode();
        LinkedList node1 = new LinkedList("x");
        listM.setNextNode(node1);
        listN.setNextNode(node1);
        LinkedList node2 = new LinkedList("y");
        node1.setNextNode(node2);
        LinkedList node3 = new LinkedList("z");
        node2.setNextNode(node3);
    }
}
﻿
最终输出结果：
链表m长度 6, 链表n长度 5
2个链表合并于结点： x
﻿