回文链表

难度:

标签:

题目描述

Implement a function to check if a linked list is a palindrome.

Example 1:

Input:  1->2
Output:  false

Example 2:

Input:  1->2->2->1
Output:  true

Follow up:
Could you do it in O(n) time and O(1) space?

代码结果

运行时间: 92 ms, 内存: 24.7 MB

/*
 * 问题描述：
 * 给定一个链表，判断它是否是回文。
 * 
 * 思路：
 * 1. 将链表的值存储在一个List中。
 * 2. 使用Stream流的方式反转List并检查是否与原List相同。
 */
import java.util.*;
import java.util.stream.*;

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class Solution {
    public boolean isPalindrome(ListNode head) {
        List<Integer> list = new ArrayList<>();
        
        // 将链表的值存储在List中
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
        
        // 使用Stream流的方式反转List并检查是否与原List相同
        List<Integer> reversedList = list.stream()
                                        .collect(Collectors.collectingAndThen(Collectors.toList(), l -> {
                                            Collections.reverse(l);
                                            return l;
                                        }));
        return list.equals(reversedList);
    }
}

解释

方法:

此题解采用了快慢指针方法来寻找链表的中点，然后反转链表的后半部分，并与前半部分进行比较以判断是否为回文链表。首先，使用两个指针f（快指针）和s（慢指针），快指针每次移动两步，慢指针每次移动一步，当快指针到达链表末端时，慢指针正好位于链表中间。如果链表长度为奇数，快指针会多出一步，此时需要将慢指针再向前移动一步，以确保后半部分较短。然后，反转从慢指针开始的链表的后半部分。最后，将原链表的头部和反转后的后半部分逐节点比较，若全部节点相等，则链表是回文的。反之，则不是回文链表。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆

在算法中，为什么选择快慢指针法来找到链表的中点，而不是通过其他方法，例如遍历一次链表记录长度后再定位中点？

▷

选择快慢指针法来找到链表的中点是为了提高效率和减少空间消耗。使用快慢指针法，我们可以在单次遍历中同时找到中点，这样只需要O(n)的时间和O(1)的额外空间。相比之下，如果先遍历一次链表记录长度，再定位中点，虽然总的时间复杂度仍为O(n)，但需要两次遍历链表，效率较低。此外，记录链表长度还需要额外的空间来存储长度信息。因此，在需要节省空间且提高效率的场景下，快慢指针法是更优的选择。

🦆

快指针移动两步，慢指针移动一步的策略是否适用于所有长度的链表，包括极端情况如只有一个或两个节点的链表？

▷

是的，这种策略适用于所有长度的链表。对于只有一个节点的链表，快指针在第一次移动时就会发现为空，因此循环结束，慢指针仍指向头节点，这时可以正确判断为回文链表。对于两个节点的链表，快指针的第一次移动会指向第二个节点，第二次移动则发现为空，结束循环，此时慢指针指向第二个节点，可以正确进行回文判断。因此，无论链表长度多短，这种快慢指针的移动策略都能正确地处理。

🦆

在链表长度为奇数时，为何要将慢指针额外向前移动一步？这一步骤对算法的正确性有何影响？

▷

在链表长度为奇数时，额外将慢指针向前移动一步是为了确保比较的是后半部分较短的那一部分与前半部分的对应部分。这是因为，当链表长度为奇数时，中间的元素不需要参与比较（因为回文的中心是一个字符）。如果不将慢指针向前移动，慢指针将从中间元素开始，后半部分将包含中间元素，导致前后比较的长度不一致，无法正确判断回文性。因此，这一步骤对保证算法正确性至关重要。

🦆

反转链表的后半部分时，是否有可能导致原链表结构被破坏，从而影响到链表的其他操作或数据安全？

▷

是的，反转链表的后半部分确实会改变原链表的结构。在这种算法实现中，原本后半部分的链表被反转，使得其节点的顺序和原来完全不同。这种结构的改变是破坏性的，如果在之后的操作中需要使用原始链表的结构，这将是一个问题。因此，在实际应用中，如果需要保持链表原有的结构不变，可能需要在完成回文判断后再次反转后半部分以复原链表，或者采用其他不改变链表结构的方法来判断回文。

回文链表

题目描述

代码结果

解释

代码细节讲解

相关问题