问答

当前位置
  • 首页
  • 问答
  • 103.Linked List Cycle II 边缘案例和时间复杂度

103.Linked List Cycle II 边缘案例和时间复杂度

  • Ta: 胡助教

题目没有限制链表元素不能有重复数值,所以官方的解法应该可以应用于以下边缘案例吧?
1. 1 -> 2 -> 3 -> 1, tail connects to node index 1
2. 1 -> 1 -> 1 -> 1, tail connects to node index 1

第一种的话我走了一遍算法,应该没问题,返回的环入口结点应该会是头结点。因为第一个结点和第四个结点虽然val域的值一样,但next域的值不一样,所以比如在某个时刻当slow指向第一个结点而fast指向最后一个结点的时候,fast != slow的判断会返回true,它俩指向的两个对象的值不一样(因为只有当这两个对象的所有实例域的值相等的情况下==才会返回true对吗)。而只有当它俩指向同一个结点(即相遇点)时第一个while循环才会结束。

同理,在第二个while循环里,当slow == head返回true的时候,一定是指向同一个结点,即环入口。而且,在这个例子里,第二个while循环并不会运行,因为一开始head == slow.next。

第二种情况,官方解法应该也是行得通的,而且两个while循环的次数和第一种情况是一样的。对吗?

第二个问题是,这个解法的时间复杂度是O(n),n为链表的元素数量,对吗?
因为第一个while循环fast一定是走完了一个环以上两个环以下的距离,然后和slow指针一起停在了环里的某个点。第二个while循环,slow走完fast没走完的第二环到环入口的距离。所以整个算法一共遍历了链表里的环两次,如果这是最坏情况,即整个链表就是一个大环,那么时间复杂度就是2n,即O(n)。

3 个回复

2019-09-14 Steven He

整个解法中,都和链表中具体存储的数值没有任何关系。fast != slow 判断fast和slow是否指向同一个节点,而不是fast和slow指向的节点的数值(val)是否相等。就算内存中存在两个节点,node_1 和 node_2,并且node_1.val == node_2.val,node_1.next == node_2.next,在判断node_1 == node_2时,也会返回false,因为它们不是同一个节点,存储在内存中不一样的位置。

其实这些引用中,存储的其实是某个对象在内存中的首地址,比如数组,int[] a = new int[1000],其中a存储的是数组中第一个元素在内存中的位置,又因为数组中的元素是相邻存储的,所以在取a[i]的时候,只要去 第一个元素的位置 + 每个元素的大小 * i 就可以取到 a[i]了。自定义的类别也是,一般对于自定义的类别,在比较两个对象的时候,实际上比较的是引用中存储的地址,所以这里只有在两个引用指向同一个地址(同一个对象)的时候才会返回true。

但是对于比如Integer之类的class,Integer a = 5, Integer b = 5.。虽然a和b是两个不同的对象,但是a == b依旧会返回true,这是因为在Integer中重载(就是重新定义)了 == 的判断方式,比较的是两个Integer 中存储的数值。

题目中自定义的ListNode很明显是没有重载==的,所以 == 的条件就是指向同一个节点。


2019-09-17 E同学

对于equals和==的区别,我有些Confused,所以我做了以下总结,老师帮忙看看对不对:

一般来说,==运算符比较的是两个变量存储的引用或者内存地址(他们是否指向同一个对象);==可用于比较primitives和objects。但是对于primitives(比如boolean, int, float),==比较的是两个变量所直接存储的数据,因为primitive变量并不指向内存地址,对吗?

而equals函数,它只可用于比较objects。Object类提供的equals函数的默认实现其实和==一样,比较的也是两个引用是否指向同一个对象/内存地址。比如:

Object obj1 = new Object();
Object obj2 = new Object();

// since the two variables are pointing to different objects, == should return false
System.out.println(obj1 == obj2);

// since the two objects are different, equals should return false **(此处equals和==的用法是没有区别的?)**
System.out.println(obj1.equals(obj2));

// since both variables point to the same object now, == and equals should return true 
obj1 = obj2;
System.out.println(obj1 == obj2);
System.out.println(obj1.equals(obj2));

但是因为Object类(包括primitive类型的外覆类像Boolean,Integer,Float;和自定义类像
String,ListNode,Employee)可以override重写各自的equals函数实现,来使他们的equals函数比较的是两个变量存储的数据或者值是否相等(即使两个变量不一定指向同一个对象)。

比如String和一个自定义类的例子:

```
class Employee {
private int id;
private String name;
public Employee(int id, String name) {
this.id = id;
this.name = name;
}

//overrides Object.equals() so it will return true if all instance fields of 2 Employee objects have same values
}

String a = new String("test");
String b = new String("test");
Employee e1 = new Employee(1, “Amy”);
Employee e2 = new Employee(1, “Amy”);

//since the two variables are pointing to different objects, "==" returns false
System.out.println(a == b);
System.out.println(e1 == e2);

//since the two strings/objects contain same content, equals() returns true
System.out.println(a.equals(b));
System.out.println(e1.equals(e2)); //true because both id and name fields hold the same value

b = a;
e2 = e1;
//since the two variables are now referencing same object, "==" returns true now
System.out.println(a == b);
System.out.println(e1 == e2);
//since the two strings/objects still contain same content, equals() returns true
System.out.println(a.equals(b));
System.out.println(e1.equals(e2));


2019-09-20 carry

1首先的区别是,equals 是方法,而 == 是操作符;
2 对于基本类型的变量来说(如 short、 int、 long、 float、 double),只能使用 == ,因为这些基本类型的变量没有 equals 方法。对于基本类型变量的比较,使用 == 比较, 一般比较的是它们的值。
3 对于引用类型的变量来说(例如 String 类)才有 equals 方法,因为 String 继承了 Object 类, equals 是 Object 类的通用方法。对于该类型对象的比较,默认情况下,也就是没有复写 Object 类的 equals 方法,使用 == 和 equals 比较是一样效果的,都是比较的是它们在内存中的存放地址。但是对于某些类来说,为了满足自身业务需求,可能存在 equals 方法被复写的情况,这时使用 equals 方法比较需要看具体的情况,例如 String 类,使用 equals 方法会比较它们的值;

我来回答

您没有权限

为提高问答质量,问答版块发言权限只向九章学员开放

登录 注册

© Jiu Zhang 2013-. All rights reserved. 京ICP备16004690号-1