今天看了ICPC-2016WF，瞬间又燃起了刷题的兴趣。研一的时候玩了好几个月，后来由于忙其它的东西就不怎么刷题了。
这道题是判断链表是否是回文，需要0(N)时间复杂度，0(1)空间复杂度。
阶梯思路想到了比较简单，先翻转一半链表，再双指针判断即可。
例如：链表的如下
1->2->3->3->2->1，总共有6个元素，可以翻转最后三个元素，得到1->2->3->1->2->3。
设定两个指针分别指向前半部分的起点与后半部分的起点，再依次比较节点上的元素是否相同即可。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
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
bool isPalindrome(ListNode* head)
{
size_t cnt = GetLength(head);
if(cnt == 1) return true;
if(cnt % 2 == 0)
{
Reverse(head,cnt/2-1);
return Judge(head, cnt/2);
}
else
{
Reverse(head,cnt/2);
return Judge(head,cnt/2+1);
}
}
bool Judge(ListNode* head, int beg)
{
ListNode* rightHead = head;
while(beg--)
{
rightHead = rightHead->next;
}
ListNode* leftHead = head;
while(leftHead && rightHead)
{
if(leftHead->val != rightHead->val)
return false;
leftHead = leftHead->next;
rightHead = rightHead->next;
}
return true;
}
int GetLength(ListNode* head)
{
size_t cnt = 0;
ListNode* p = head;
while(p!=NULL)
{
cnt++;
p = p->next;
}
return cnt;
}
void Reverse(ListNode* head, int beg)
{
ListNode* st = head;
while(beg--)
{
st = st->next;
}
ListNode* pre = st->next;
ListNode* cur = pre->next;
ListNode* tmp = NULL;
while(cur)
{
pre->next = cur->next;
tmp = st->next;
st->next = cur;
cur->next = tmp;
cur = pre->next;
}
}
};