目录
题目要求
对于一个单链表,设计一个时间复杂度为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
代码验证:
算法的时间和空间复杂度:
时间复杂度(大O渐进表示法):O(N)
空间复杂度(大O渐进表示法):O(1)