week8-homework

关注

发布于: 2021 年 01 月 12 日

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

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

算法实现如下，对于给定的两个链表，找到长的链表，并移动指针使得两个链表指针起点到终点是一样的距离，然后将两个指针同时按照一样的步长（1）向后移动，如果两个指针指向同一个节点，就是两条链表相加的节点，否则两个链表无相交。时间复杂度是 O(m+n)，空间复杂度是 O(1)

package com.algorithm.link;
/** * @author lvlin * @date 2021-01-12 10:58 AM */public final class CrossLinks {
    /**     * Find the crossed node between two links     * @param a first node for the first link     * @param b first node for the second link     * @return the crossed node or null for not crossed     */    public Node findCrossedNode(Node a, Node b){        // parameter checking        if (null == a || null == b) {            return null;        }        if (a.getValue() == b.getValue()) {            return a;        }
        // find the length of two links        int lenA = 0;        int lenB = 0;        Node pA = a;        while (pA.getNext() != null){            lenA++;            pA = pA.getNext();        }        Node pB = b;        while (pB.getNext() != null) {            lenB++;            pB = pB.getNext();        }
        // move the long link firstly to same length        pA = a;        pB = b;        if (lenA > lenB) {            for (int i = 0; i < lenA - lenB; i++) {                pA = pA.getNext();            }        } else if (lenA < lenB) {            for (int i = 0; i < (lenB - lenA); i++) {                pB = pB.getNext();            }        }
        // detect the crossing node        while (pA != null && pB != null){            if (pA == pB){                return pA;            }            pA = pA.getNext();            pB = pB.getNext();        }
        // no crossing at the end.        return null;    }}

复制代码

package com.algorithm.link;
/** * @author lvlin * @date 2021-01-12 10:59 AM */public final class Node {    private final int value;    private Node next;
    public Node(final int value, Node next) {        this.value = value;        this.next = next;    }
    public int getValue() {        return value;    }
    public Node getNext() {        return next;    }
    public void setNext(final Node next) {        this.next = next;    }}

复制代码

package com.algorithm.link;
import org.apache.commons.lang3.tuple.Pair;import org.junit.jupiter.api.Test;
import java.util.HashMap;import java.util.Map;
import static org.junit.jupiter.api.Assertions.*;
/** * @author lvlin * @date 2021-01-12 11:11 AM */class CrossLinksTest {
    @Test    void should_find_crossed_in_the_middle() {        checkCross(new int[]{1, 3, 5, 6, 7, 9}, new int[]{2, 4, 5, 6, 7, 9}, new Node(5, null));    }
    @Test    void should_find_crossed_in_the_beginning() {        checkCross(new int[]{1, 2}, new int[]{1, 4}, new Node(1, null));    }
    @Test    void should_find_crossed_in_the_end() {        checkCross(new int[]{1, 2, 3, 9}, new int[]{7, 8, 9}, new Node(9, null));    }
    @Test    void should_find_no_crossed() {        checkCross(new int[]{1}, new int[]{2}, null);        checkCross(new int[]{1, 2}, new int[]{3, 4}, null);    }
    @Test    void should_handle_empty_links() {        // empty node        checkCross(new int[]{}, new int[]{}, null);        checkCross(new int[]{}, new int[]{1}, null);    }
    private void checkCross(final int[] nodes1, final int[] nodes2, final Node expected) {        Pair<Node, Node> links = buildLinks(nodes1, nodes2);        Node crossed = new CrossLinks().findCrossedNode(links.getLeft(), links.getRight());        if (expected == null) {            assertNull(crossed);        } else {            assertEquals(crossed.getValue(), expected.getValue());        }    }

    private Pair<Node, Node> buildLinks(final int[] nodes1, final int[] nodes2) {        Map<Integer, Node> nodes = new HashMap<>();        buildNodesMap(nodes1, nodes);        buildNodesMap(nodes2, nodes);
        linkNodes(nodes1, nodes);        linkNodes(nodes2, nodes);
        Node a, b;        if (nodes1.length > 0) {            a = nodes.get(nodes1[0]);        } else {            a = null;        }        if (nodes2.length > 0) {            b = nodes.get(nodes2[0]);        } else {            b = null;        }
        return Pair.of(a, b);    }
    private void linkNodes(final int[] nodesValues, final Map<Integer, Node> nodes) {        for (int i = nodesValues.length - 1; i >= 1; i--) {            Node nextNode = nodes.get(nodesValues[i]);            Node preNode = nodes.get(nodesValues[i - 1]);            preNode.setNext(nextNode);        }    }
    private void buildNodesMap(final int[] nodesValue, final Map<Integer, Node> nodes) {        for (final int v : nodesValue) {            if (nodes.containsKey(v)) {                continue;            }            nodes.put(v, new Node(v, null));        }    }
}