架构师训练营第八章作业
作业:
有两个单向链表(链表长度分别为 m,n),这两个单向链表有可能在某个元素合并,如下图所示的这样,也可能不合并。现在给定两个链表的头指针,在不修改链表的情况下,如何快速地判断这两个链表是否合并?如果合并,找到合并的元素,也就是图中的 x 元素。
请用(伪)代码描述算法,并给出时间复杂度和空间复杂度。
时间复杂度O(m + n)
空间复杂度O(1)
作业:
有两个单向链表(链表长度分别为 m,n),这两个单向链表有可能在某个元素合并,如下图所示的这样,也可能不合并。现在给定两个链表的头指针,在不修改链表的情况下,如何快速地判断这两个链表是否合并?如果合并,找到合并的元素,也就是图中的 x 元素。
请用(伪)代码描述算法,并给出时间复杂度和空间复杂度。
public class ListNode { int val; ListNode next; ListNode(int x) { val = x; next = null; } }public ListNode getIntersectionNode(ListNode nodePre, ListNode nodeNext) { if (nodePre == null || nodeNext == null) { return null; } ListNode np = nodePre; ListNode nn = nodeNext; while (np != nn) { np = (np == null) ? nodeNext : np.next; nn = (nn == null) ? nodePre : nn.next; } return np;}
时间复杂度O(m + n)
空间复杂度O(1)
折翼的小鸟还能飞 2019.04.29 加入
擅长于基础框架搭建、微服务、设计模式
促进软件开发及相关领域知识与创新的传播
评论 (1 条评论)