## Algorithm-Easy

Posted by Jae on September 23, 2018

### 1、题目

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

Example 1:

 Input: 1->2
Output: false


Example 2:

Input: 1->2->2->1
Output: true


### 4、分析

1、首先遍历链表计算节点数量;
2、计算中间节点的位置(len/2);
3、将right指针移动到中间节点所在位置;
4、反转后半部分链表;
5、以right!=nullptr为条件，lift和right同时后移并逐一比较。


### 5、实现

[c++]
class Solution {
public:
//反转单链表
{

while (forward != nullptr)
{
tail -> next = forward -> next;
forward = tail -> next;
}
}

int count = 0;
while (p != nullptr)
{
++count;
p = p->next;
}
if (count == 0 || count == 1) {return true;}

int mid = (count % 2 == 0) ? count/2 : count/2+1;
while (mid>0)
{
i = i->next;
--mid;
}
while (new_start!=nullptr)
{
if (j->val != new_start->val) {return false;}
j = j->next;
new_start = new_start->next;
}
return true;
}
};

[Java]
{
return true;
}

// 找到单链表的中间节点
while (j.next != null && j.next.next != null)
{
i = i.next;
j = j.next.next;
}
i = i.next;
ListNode t = i;
ListNode prev = null;
while (t != null)
{
t = t.next;
i.next = prev;
prev = i;
i = t;
}
// 反转完成
while (prev != null)
{
{
return false;
}
prev = prev.next;
}
return true;
}


### 6、他山之石

拿物体的运动来说明：



### 7、实现

bool isPalindrome2(ListNode* head) {

while (fast->next && fast->next->next)
{
slow = slow->next;
fast = fast->next->next;
}
ListNode* right = slow->next;

while (right)
{
if (right->val != left->val) {return false;}
left = left->next;
right = right->next;
}

return true;
}


### 8、收获

< script src = " / js / bootstrap.min.js " >