class Solution { public boolean isPalindrome(ListNode head) { // 快慢指针找中点 ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } // 反转后半部分 ListNode pre = null; while (slow != null) { ListNode next = slow.next; slow.next = pre; pre = slow; slow = next; } // 前后两段比较是否一致 ListNode node = head; while (pre != null) { if (pre.val != node.val) { return false; } pre = pre.next; node = node.next; } return true; }这段代码的时间复杂度和空间复杂度
时间: 2023-12-30 16:01:59 浏览: 32
这段代码的时间复杂度为O(n),其中n为链表的长度。快慢指针找中点和反转后半部分都需要遍历一遍链表,时间复杂度均为O(n/2),前后两段比较也需要遍历一遍链表,时间复杂度为O(n/2)。因此,总的时间复杂度为O(n/2) + O(n/2) + O(n) = O(n)。
空间复杂度为O(1),因为只使用了常数级别的额外空间,不随链表长度n的增加而增加。
相关问题
给一个单向链表,若其中包含环,请完善EntryNodeOfLoop方法找出该链表的环的入口结点,否则,输出null。要求空间复杂度为O(1) public class ListNode { //链表的数据结构 int val; ListNode next = null; } public ListNode EntryNodeOfLoop(ListNode pHead) { }
好的,这是一个经典的链表问题。具体解决方法如下:
1. 首先判断链表中是否有环。我们可以用快慢指针来判断,快指针每次走两步,慢指针每次走一步,如果存在环,那么快指针一定会追上慢指针。
2. 如果链表中存在环,我们需要找到环的入口节点。我们可以使用两个指针,一个指针从链表头节点开始,另一个指针从快慢指针相遇的节点开始,两个指针每次都走一步,当它们相遇时,就是环的入口节点。
完整的代码如下:
```
public ListNode EntryNodeOfLoop(ListNode pHead) {
ListNode slow = pHead;
ListNode fast = pHead;
boolean hasLoop = false;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
hasLoop = true;
break;
}
}
if (!hasLoop) {
return null;
}
ListNode p1 = pHead;
ListNode p2 = slow;
while (p1 != p2) {
p1 = p1.next;
p2 = p2.next;
}
return p1;
}
```
时间复杂度为O(n),空间复杂度为O(1)。
用java代码写一个使用快慢指针判断链表是否有环的demo
好的,下面是使用快慢指针判断链表是否有环的 Java 代码示例:
```java
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while (slow != fast) {
if (fast == null || fast.next == null) {
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}
}
```
其中,ListNode 是定义链表节点的类,Solution 类中的 hasCycle 方法就是判断链表是否有环的实现方法。在方法中,使用了两个指针 slow 和 fast,分别指向链表的头节点和头节点的下一个节点。然后,不断地让这两个指针向前移动,如果链表存在环,那么 fast 指针一定会在某个时刻追上 slow 指针,此时就可以判断链表存在环;如果链表不存在环,那么 fast 指针会先到达链表结尾,此时就可以判断链表不存在环。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)