234. 回文链表

转载自Leet Code

题目描述

请判断一个链表是否为回文链表。

示例 1: >输入: 1->2 >输出: false

示例 2: >输入: 1->2->2->1 >输出: true

进阶：

你能否用 \(O(n)\) 时间复杂度和 \(O(1)\) 空间复杂度解决此题？

---

我的代码

\(T(N) = O(N)\), \(S(N) = O(1)\)

{.line-numbers}

/**
 * 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 MySolution234 
{
    public boolean isPalindrome(ListNode head) 
    {
    	if (head==null||head.next==null) return true;
    	if (head.next.next==null) return head.val==head.next.val;
    	
    	ListNode p = head; int length = 0;
    	while (p!=null)
    	{
    		length++; p = p.next; 
    	}
    	
    	ListNode prev = head; ListNode post;
    	for (int i=0; i<length/2; i++)
    		prev = prev.next;
    	p = prev.next; post = p.next;
    	
    	prev.next = null; p.next = prev;
    	while (post!=null)
    	{
    		prev = p;
    		p = post;
    		post = post.next;
    		p.next = prev;
    	}
    	
    	ListNode pointer = head;
    	for (int i=0; i<length/2; i++)
    	{
    		if (p.val!=pointer.val) return false;
    		p = p.next; pointer = pointer.next;
    	}
    	return true;
    }
}

思路: 递归

\(T(N) = O(N)\), \(S(N) = O(N)\)

递归遍历节点的方式如下。

function print_values_in_reverse(ListNode head)
    if head is NOT null
        print_values_in_reverse(head.next)
        print head.val

因此，如果我们能利用递归来反向遍历节点， 同时使用一个递归函数外面的变量向前迭代， 就可以判断链表是否为回文的。

---

代码

{.line-numbers}

class Solution234
{
	ListNode frontPointer;
    public boolean isPalindrome(ListNode head) 
    {
    	frontPointer = head;
    	return recursivelyCheck(head);
    }
    boolean recursivelyCheck(ListNode backPointer)
    {
    	if (backPointer!=null) 
    	{
			// 首先从这里开始back指针一直跑到尾节点(backPointer.next==null)
    		if (!recursivelyCheck(backPointer.next)) 
    			return false;
			// back指针从尾节点开始取值，front指针从头节点开始取值
    		if (backPointer.val!=frontPointer.val) 
    			return false;
			// back指针向上一层递归追溯之前向后迭代front指针
    		frontPointer = frontPointer.next;
    	}
		// 递归到达边界(backPointer==null)，并返回true
    	return true;
    }
}