写点什么

第八周链表练习

用户头像
李广富
关注
发布于: 2020 年 07 月 29 日

题目:

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

请用(伪)代码描述算法,并给出时间复杂度和空间复杂度。



定义节点类:

package com.li.linked;
public class ListNode {
int val;
ListNode next = null;
public ListNode(int val) {
this.val = val;
}
}



定义算法类,用于计算合并的节点:

package com.li.linked;
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
//有为空的情况
if (pHead1 == null || pHead2 == null) return null;
//第一个节点就重合的情况
if (pHead1 == pHead2) return pHead1;
ListNode p1 = pHead1;
ListNode p2 = pHead2;
int len1 = getListLength(pHead1);
int len2 = getListLength(pHead2);
// 在长的链表上先走几步,让二者等长
if (len1 > len2) {
for (int i = 0; i < len1 - len2; i++) {
p1 = p1.next;
}
} else if (len1 < len2) {
for (int j = 0; j < len2 - len1; j++) {
p2 = p2.next;
}
}
//如果存在公共节点,二者就不会执行到空再退出;此外,两个指针对应的后续的节点个数
while (p1 != null && p2 != null) {
//已经是相等的,因此只判断一个不为空就行了,两个也行。
if (p1 == p2) {
return p1;
} else {
p1 = p1.next;
p2 = p2.next;
}
}
return null;
}
public int getListLength(ListNode pHead) {
if (pHead == null) return 0;
ListNode p = pHead;
int len = 0;
while (p != null) {
len++;
p = p.next;
}
return len;
}
}

时间复杂度为o(m+n),空间复杂度为o(1)。

用户头像

李广富

关注

还未添加个人签名 2019.11.12 加入

还未添加个人简介

评论

发布
暂无评论
第八周链表练习