数据结构 ——— 单链表oj题：链表的回文结构

题目要求

手搓简易单链表

代码实现

题目要求

对于一个单链表，设计一个时间复杂度为O(N)，空间复杂度为O(1)的算法，判断其是否为回文结构，给定一个链表的头指针 head，返回一个 bool 值，代表其是否为回文结构

举例说明：

链表：1->2->3->2->1

返回：true

链表：1->2->3->1

返回：false

手搓简易单链表

代码演示：

struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n1);
struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n2);
struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n3);
struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n4);
struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n5);
struct ListNode* n6 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n6);
struct ListNode* n7 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n7);
struct ListNode* n8 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n8);n1->val = 1;
n2->val = 2;
n3->val = 3;
n4->val = 4;
n5->val = 4;
n6->val = 3;
n7->val = 2;
n8->val = 1;n1->next = n2;
n2->next = n3;
n3->next = n4;
n4->next = n5;
n5->next = n6;
n6->next = n7;
n7->next = n8;
n8->next = NULL;

代码实现

代码演示：

// 找到中间节点
struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* slow = head;struct ListNode* fast = head;while (fast != NULL && fast->next != NULL){slow = slow->next;fast = fast->next->next;}return slow;
}// 逆置链表（头插法）
struct ListNode* reverseList(struct ListNode* head)
{if (head == NULL)return NULL;struct ListNode* rhead = NULL;struct ListNode* cur = head;struct ListNode* next = cur->next;while (cur != NULL){cur->next = rhead;rhead = cur;cur = next;if (next != NULL)next = next->next;}return rhead;
}// 链表的回文结构
bool chkPalindrome(struct ListNode* head)
{if (head == NULL)return true;// 找到中间节点struct ListNode* mid = middleNode(head);// 从中间节点逆置struct ListNode* rmid = reverseList(mid);struct ListNode* cur = head;while (rmid != NULL){if (cur->val != rmid->val)return false;cur = cur->next;rmid = rmid->next;}return true;
}

代码解析：

先找到单链表的中间节点 mid ，再从中间节点开始往后逆置节点，cur 节点指针和 rmid 节点指针同时往后走，只要val 不同时就表示不是回文结构，返回 false ，如果一直没有返回，那么就代表链表是回文结构，返回 true

代码验证：