p234

发表于 | 分类于 |

LeetCode p234 Palindrome Linked List 题解

1.题目：

Given a singly linked list, determine if it is a palindrome.

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

题意：

判断一个单向链表是否回文

2.解题思路:

使用递归，再逆序匹配，也可以反转链表。

3.代码

[title] [] [url] [link text]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int flag = 0;
	public ListNode a;

	public boolean isPalindrome(ListNode head) {
		if (head == null)
			return true;
		a = head;
		dp(head);
		return flag == 0;
	}

	public void dp(ListNode head) {

		if (head.next != null) {
			dp(head.next);
		}
		if (flag == 1)
			return;
		if (a.val != head.val) {
			flag = 1;
		}
		a = a.next;
	}
}

4.一些总结：