-
Notifications
You must be signed in to change notification settings - Fork 0
/
223. 回文链表.cpp
87 lines (82 loc) · 1.91 KB
/
223. 回文链表.cpp
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
// class Solution {
// public:
// /*
// * @param head: A ListNode.
// * @return: A boolean.
// */
// bool isPalindrome(ListNode * head) {
// // write your code here
// int len = 0;
// ListNode *p = head;
// while(p!=NULL)
// {
// p = p->next;
// len++;
// }
// p = head;
// ListNode *newHead, *temp;
// newHead = temp = NULL;
// for(int i=0; i<(len/2); ++i)
// {
// temp = p->next;
// p->next = newHead;
// newHead = p;
// p = temp;
// }
// if(len%2 != 0)
// p = p->next;
// while(newHead!=NULL && p!=NULL)
// {
// if(newHead->val != p->val)
// return false;
// newHead = newHead->next;
// p = p->next;
// }
// return true;
// }
// };
class Solution {
public:
/*
* @param head: A ListNode.
* @return: A boolean.
*/
bool isPalindrome(ListNode * head) {
// write your code here
ListNode *p = head;
int len = 0;
while(p!=NULL)
{
len++;
p = p->next;
}
ListNode *s, *temp;
s = NULL;
p = head;
for(int i=1; i<=len/2; i++)
{
temp = p->next;
p->next = s;
s = p;
p = temp;
}
if(len%2 != 0)
p = p->next;
while(s!=NULL && p!=NULL)
{
if(s->val != p->val)
return false;
s = s->next;
p = p->next;
}
return true;
}
};