单链表的问题（2）
1.对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
这个我们可以运用双指针来解决这个问题 ，一个用slow，一个为fast
ListNode* tou(ListNode* head)
{
ListNode* n1 = NULL;
ListNode* n2 = head;
ListNode* n3 = head->next;
while (n2)
{
n2->next = n1;
n1 = n2;
n2 = n3;
if (n3)
n3 = n3->next;
}
return n1;
}这里下面用到的链表的反转，如果不太清楚可以看上一篇文章。 （以上是反转的代码）
bool chkPalindrome(ListNode* a) {
ListNode* slow = a;
ListNode* fast = a;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
ListNode* head = tou(slow);
while (head)
{
if (head->val != a->val)
{
return false;
}
head = head->next;
a = a->next;
}
return true;这里是有一个规律，如果是回文序列的话slow一定会走到 中间的右边的节点，就是如图的右边的3的节点，
也可以通过这个案例看到这样的情况。
这里用到的反转是将4后面的反转，形成如图所示的情况
这时通过反转代码，返还的是最右边1的地址，而我们还知道开头的地址，所以通过while函数来进行比较，来得到我们所需要的结果。
2.实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。
这里我们可以先让一个指针多走k步，这样slow与fast之间差k步，这以后都是我们要找的
例如：找倒数第三个
如上图所示，当fast到NULL时，slow正好是在我们所要的倒数第三个。
ListNode* slow = head;
ListNode* fast = head;
if (fast == NULL)
{
return NULL;
}
while (k--)
{
fast = fast->next;
}
while (fast)
{
slow = slow->next;
fast = fast->next;
}
return slow->val;第一步是判断不是空链表（代码便如图所示）