链表的回文结构（链表的中间节点+反转链表）

要解决链表的回文结构：首先需要求中间节点，其次是会反转链表。

一.链表的中间节点

链表的中间节点

思路1：暴力求解

1. 求出链表的长度。
2. 求出要返回的中间节点的位置（除2+1），遍历链表返回节点指针即可。
3. 注意：兼容奇数个节点与偶数个节点。

typedef struct ListNode ListNode;struct ListNode* middleNode(struct ListNode* head) 
{ListNode* cur = head;int listLength = 0; while(cur){//求链表的长度listLength++;cur = cur->next;}//链表中间节点的位置int middle = listLength / 2 + 1;int i = 1; //注意：非i=0cur = head;while(i < middle){i++;cur = cur->next;}return cur;
}

思路2：快慢指针

1. 定义两个指针fast、slow保存链表头节点的地址。
2. 进入循环，fast指针一次走两个节点，slow指针一次走一个节点，当fast != NULL && fast->next != NULL时循环继续，否则循环结束。

情况1.含有奇数个节点

情况2.含有偶数个节点

typedef struct ListNode ListNode;struct ListNode* middleNode(struct ListNode* head)
{//快慢指针：慢指针一次走一步，快指针一次走两步ListNode* fast = head;ListNode* slow = head;//注意循环继续的条件是&&而不是||，且fast与fast->next的位置不能交换while (fast != NULL && fast->next != NULL){fast = fast->next->next;slow = slow->next;}return slow;
}

二.返回倒数第k个节点

返回倒数第k个节点

思路1：暴力求解

1. 遍历链表求链表的长度length。
2. 倒数第k个节点，等价于从前往后的第length - k个节点。
3. 再次遍历链表找到第length - k个节点，返回节点指针即可。

typedef struct ListNode ListNode;int kthToLast(struct ListNode* head, int k)
{//1.遍历链表求出链表长度，再遍历一次链表，找到返回值int size = 0;ListNode* cur = head;while(cur){size++;cur = cur->next;}int i = 0;cur = head;while(i < size - k){cur = cur->next;i++;}return cur->val;
}

思路2：快慢指针

1. 定义两个指针fast、slow保存链表头节点的地址。
2. fast指针先走k个节点。
3. 进入循环，fast与slow指针各自每次走一个节点，当fast != NULL时循环继续，否则循环结束。

typedef struct ListNode ListNode;int kthToLast(struct ListNode* head, int k)
{//2.快慢指针：快指针先走k步，然后快指针一次走一步，慢指针一次走一步ListNode* fast = head;ListNode* slow = head;for (int i = 0; i < k; i++){fast = fast->next;}while (fast != NULL){fast = fast->next;slow = slow->next;}return slow->val;
}

三.反转链表

反转链表

思路1：头插法

1. 创建新链表 newHead = NULL。
2. 遍历原链表，逐个节点头插倒新链表中。

typedef struct ListNode ListNode;struct ListNode* reverseList(struct ListNode* head) 
{//1.创建新链表，遍历原链表，逐个头插ListNode* newHead = NULL, *cur = head;while(cur){//头插ListNode* next = cur->next;cur->next = newHead;newHead = cur;cur = next;}return newHead;
}

思路2：反转指针的指向

typedef struct ListNode ListNode;struct ListNode* reverseList(struct ListNode* head) 
{//2.创建三个指针，反转指针的指向if(head == NULL){return NULL;}ListNode* n1 = NULL, *n2 = head, *n3 = n2->next;while(n2){n2->next = n1;n1 = n2;n2 = n3;if(n3 != NULL){n3 = n3->next;}   }return n1;
}

四.链表的回文结构

链表的回文结构

思路1：利用数组，判断是否回文

class PalindromeList {
public://判断数组是否满足回文结构bool isReverse(int arr[], int left, int right){while(left < right){if(arr[left] != arr[right]){return false;}left++;right--;}return true;}bool chkPalindrome(ListNode* A){int arr[900];ListNode* cur = A;int i = 0, listLength = 0;while(cur){arr[i++] = cur->val;//将链表中的值保存到数组中cur = cur->next;listLength++;//求链表的长度}return isReverse(arr, 0, listLength - 1);}
};

思路2：求链表的中间节点+反转链表

1. 寻找链表的中间节点 mid。
2. 将中间节点 mid 以及之后的节点组成的链表反转。
3. 遍历反转后的链表，当一个一个与原链表的数据域对比，若相同则是回文结构。

情况1.含有奇数个节点：

情况2.含有偶数个节点：

class PalindromeList {
public:ListNode* findMidNode(ListNode* phead){ListNode* fast = phead;ListNode* slow = phead;while(fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;}ListNode* reverseList(ListNode* phead){ListNode* n1, *n2, *n3;n1 = NULL, n2 = phead, n3 = n2->next;while(n2){n2->next = n1;n1 = n2;n2 = n3;if(n3 != NULL){n3 = n3->next;}         }return n1;}bool chkPalindrome(ListNode* A) {//1.找链表的中间节点ListNode* mid = findMidNode(A);//2.反转中间节点以及之后的节点组成的链表ListNode* right = reverseList(mid);//3.遍历反转链表，与原链表进制值的比较ListNode* left = A;while(right){if(right->val != left->val){return false;}right = right->next;left = left->next;}return true;}
};