每日一题——回文链表

回文链表

题目链接

回文结构即字符串正序逆序完全一致，如“1 2 3 4 3 2 1”，那么我们就要想办法同时比较链表头和链表尾的元素，看其是否相等。

下面介绍一种最常用的方法：

---

思路

如果我们仔细观察回文结构，就会得到一个结论：

将一个回文结构从正中间分隔，再将后半部分逆序，那么前半部分就一定等于后半部分。

我们可以分链表长度为奇数和偶数讨论：

当长度为偶数：

当长度为奇数：

• 那么**，第一步就先要得到链表的中间节点。我们可以用快慢指针**来实现：

定义两个指针fast、slow，同时指向链表头，slow每次走一个，fast每次走两个节点，当fast->next == NULL 或者 fast == NULL时，slow就走到中间节点了

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

• 第二步，就是反转以slow节点为头的链表，如果对单链表反转还不太了解的朋友，建议先看看👉反转单链表

struct ListNode* reverseList(struct ListNode* head)
{if (head == NULL)return NULL;struct ListNode* newHead = (struct ListNode*)malloc(sizeof(struct ListNode));newHead->next = head;struct ListNode* cur = head;while (cur->next){struct ListNode* curNext = cur->next;cur->next = curNext->next;curNext->next = newHead->next;newHead->next = curNext;}struct ListNode* retHead = newHead->next;free(newHead);return retHead;
}

• 第三步，我们用指针mid来接受slow后链表反转过后的头，接下来，从原来链表的头和mid开始比较，只要遇到不相等的情况，就返回false，否则返回true。

struct ListNode* mid = reverseList(slow->next);
struct ListNode* cur1 = head;
struct ListNode* cur2 = mid;while (cur1 && cur2)
{if (cur1->val != cur2->val){return false;}cur1 = cur1->next;cur2 = cur2->next;
}return true;

• 最后一步，**在返回之前，需要将链表还原，**毕竟在现实生活中，没有人想再调用这个函数时改变原来的链表结构。但是，如果我们就按上面的操作进行还原，那么就会出现一系列的问题，我们拿下图说明

判断过后，链表的结构是这样的：

如果我们要将链表还原，那么问号处的节点的后面应该链接到reverseList(mid)的返回值，但问题是之前我们并没有保存问号处的节点。所以，我们可以对找到链表中间节点这一操作进行改进：

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

这样slow就会停留在问号处的位置，反转链表的时候就反转以slow->next为头的链表就行了

实现代码

struct ListNode* reverseList(struct ListNode* head)	//反转链表
{if (head == NULL)return NULL;struct ListNode* newHead = (struct ListNode*)malloc(sizeof(struct ListNode));newHead->next = head;struct ListNode* cur = head;while (cur->next){struct ListNode* curNext = cur->next;cur->next = curNext->next;curNext->next = newHead->next;newHead->next = curNext;}struct ListNode* retHead = newHead->next;free(newHead);return retHead;
}bool isPalindrome(struct ListNode* head){struct ListNode* slow = head;struct ListNode* fast = head;while (fast->next && fast->next->next)	//找到中间节点的前一个节点{slow = slow->next;fast = fast->next->next;}//反转以中间节点为头的链表//将返回值赋给midstruct ListNode* mid = reverseList(slow->next);	struct ListNode* cur1 = head;struct ListNode* cur2 = mid;bool ret = true;	//设置返回值while (cur1 && cur2){if (cur1->val != cur2->val){ret = false;	//只要出现不相等的情况，就将返回值设为false，推出比较break;}cur1 = cur1->next;cur2 = cur2->next;}//还原链表mid = reverseList(mid);slow->next = mid;//返回return ret;
}