单向链表合并

关注

发布于: 2020 年 11 月 15 日

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

架构师训练营第 1 期第 8 周课后思考题，单向链表合并，其实是 LeetCode 的 160 题，Intersection of Two Linked Lists。

官方给出了三个解题思路：

Brute Force 暴力解法，双重循环遍历两个链表，时间复杂度 O(mn)，空间复杂度 O(1)
Hash Table 哈希表，将一个链表转为 Hash 表，然后遍历另一个链表，时间复杂度 O(m+n)，空间复杂度 O(m) 或 O(n)
Two Pointers 双指针，同时遍历两个链表，遍历到一条链表终点之后，续到另一条链表头部，比较两个指针，如果相等，则为交点

第二个解法的代码

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { *         val = x; *         next = null; *     } * } */public class Solution {    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {        // boundary check        if (headA == null || headB == null) {            return null;        }        ListNode pA = headA;        ListNode pB = headB;        // if a & b have different len,        // then we will stop the loop after second iteration        while (pA != pB) {            // for the end of first iteration,            // we just reset the pointer to the head of another linkedlist            pA = pA == null ? headB : pA.next;            pB = pB == null ? headA : pB.next;        }        return pA;    }}

复制代码

发布于: 2020 年 11 月 15 日阅读数: 26

原文链接:【http://xie.infoq.cn/article/b1368eb69eb2e3bae93f1d3af】。

escray

关注

Let's Go 2017.11.19 加入

在学 Elasticsearch 的项目经理

发布

暂无评论

创作场景

单向链表合并

escray

评论