力扣hot100 回文链表 双指针 递归 反转链表

Problem: 234. 回文链表

思路

👨?🏫 参考题解

Code

? 时间复杂度: $O(n)$
🌎 空间复杂度: $O(n)$

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
	public boolean isPalindrome(ListNode head)
	{
		boolean ans = true;
		List<Integer> list = new ArrayList<>();
		ListNode x = head;
		while (x != null)
		{
			list.add(x.val);
			x = x.next;
		}
		int l = 0;
		int r = list.size() - 1;
		while (l < r)
		{
			if (list.get(l++) != list.get(r--))
				return false;
		}
		return ans;
	}
}

💖 递归

? 时间复杂度: $O(n)$
🌎 空间复杂度: $O(n)$

class Solution {
//	递归
	public boolean isPalindrome(ListNode head)
	{
		frontPointer = head;
		return recur(head);
	}

	ListNode frontPointer;//前指针
	/**
	 * 返回 currentNode 与 对应的frontPointer 是否相同
	 * 
	 * @param currentNode //后指针
	 * @return 所有前后指针是否相等
	 */
	private boolean recur(ListNode currentNode)
	{
		if (currentNode != null)
		{
//			递归到最后一个节点，这里就会返回 true，然后走下边的逻辑
//			然后开始回溯，从最后一个节点 往前回溯 
			if (!recur(currentNode.next))
				return false;
			
//			判断 第1个 和 最后1个，第2个 和 倒数第2个 …… 是否相等
			if (currentNode.val != frontPointer.val)
				return false;
			frontPointer = frontPointer.next;
		}
		return true;
	}
}

💖 快慢指针 + 反转链表

? 时间复杂度: $O(n)$
🌎 空间复杂度: $O(1)$

class Solution:

    def isPalindrome(self, head: ListNode) -> bool:
        if head is None:
            return True

        # 找到前半部分链表的尾节点并反转后半部分链表
        first_half_end = self.end_of_first_half(head)
        second_half_start = self.reverse_list(first_half_end.next)

        # 判断是否回文
        result = True
        first_position = head
        second_position = second_half_start
        while result and second_position is not None:
            if first_position.val != second_position.val:
                result = False
            first_position = first_position.next
            second_position = second_position.next

        # 还原链表并返回结果
        first_half_end.next = self.reverse_list(second_half_start)
        return result    

    def end_of_first_half(self, head):
        fast = head
        slow = head
        while fast.next is not None and fast.next.next is not None:
            fast = fast.next.next
            slow = slow.next
        return slow

    def reverse_list(self, head):
        previous = None
        current = head
        while current is not None:
            next_node = current.next
            current.next = previous
            previous = current
            current = next_node
        return previous