架构训练营第八周作业

关注
发布于: 2020 年 07 月 28 日
有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，如下图所示的这样，也可能不合并。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。
请用（伪）代码描述算法，并给出时间复杂度。
public class LinkedListMerge {
    public static void main(String args[]) {
        Node head1 = genLinkedList('a', 'b', 'f', 'x', 'a', 'z');
        Node head2 = genLinkedList('d', 'e', 'f', 'x', 'y', 'z');
        Node mergePoint = findMerge(head1, head2);
        System.out.println(mergePoint != null ? mergePoint.getC() : "Can't merge");
    }
    private static Node genLinkedList(Character ... chars) {
        Node head = new Node();
        Node p = head;
        for (Character c : chars) {
            Node n = new Node();
            n.setC(c);
            p.setNext(n);
            p = p.next;
        }
        return head.next;
    }
    private static Node findMerge(Node head1, Node head2) {
        if (head1 == null || head2 == null)
            return null;
        int len1 = getLength(head1);
        int len2 = getLength(head2);
        int base = Math.min(len1, len2);
        Node rebase1 = rebase(head1, len1 - base);
        Node rebase2 = rebase(head2, len2 - base);
        boolean isContinue = false;
        boolean isFirst = false;
        Node result = null;
        while(rebase1 != null && rebase2 != null) {
            if (!rebase1.getC().equals(rebase2.getC())) {
                isContinue = false;
                isFirst = false;
            } else {
                if (!isFirst) {
                    isFirst = true;
                    result = rebase1;
                }
                isContinue = true;
            }
            rebase1 = rebase1.next;
            rebase2 = rebase2.next;
        }
        return isContinue ? result : null;
    }
    /**
     * 把head往后移动offset位置
     */
    private static Node rebase(Node head, int offset) {
        for (int i = 0; i < offset; i++) {
            head = head.next;
        }
        return head;
    }
    private static int getLength(Node head) {
        int i = 0;
        while(head != null) {
            i++;
            head = head.next;
        }
        return i;
    }
    static class Node {
        private char c;
        private Node next;
        public Character getC() {
            return c;
        }
        public void setC(Character c) {
            this.c = c;
        }
        public Node getNext() {
            return next;
        }
        public void setNext(Node next) {
            this.next = next;
        }
    }
}
        整体思路是：将两个链表从尾部对齐，然后从较短链表的头部位置开始搜索，如果能够找到到尾部的公共连续子串，就返回结果。
        时间复杂度分析：getLength函数O(n)，rebase函数O(n)，在findMerge中找剩余链表，也是顺序往后查找，所以时间复杂度也是O(n)。综上，算法整体时间复杂度O(n)。运行结果：
('a', 'b', 'f', 'x', 'a', 'z');
('d', 'e', 'f', 'x', 'y', 'z')
结果：z
﻿
发布于: 2020 年 07 月 28 日阅读数: 56
张锐

关注
还未添加个人签名 2018.08.07 加入
还未添加个人简介
评论 (1 条评论)

发布
创作场景

架构训练营第八周作业

张锐

评论 (1 条评论)
