本文共 697 字,大约阅读时间需要 2 分钟。
对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。
给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结构。保证链表长度小于等于900。
测试样例:
1->2->2->1
返回:true
快慢指针
反转链表
需要注意一点防止反转后链表成环的问题
class PalindromeList {public: bool chkPalindrome(ListNode* A) { ListNode*slow = A, *fast = A, *prev = NULL;//prev防止链表成环 while (fast&&fast->next) { prev = slow; slow = slow->next; fast = fast->next->next; } prev->next = NULL;//防止链表成环 ListNode*newhead = NULL, *cur = slow; while (cur) { ListNode*next = cur->next; cur->next = newhead; newhead = cur; cur = next; } slow = newhead; while (A) { if (A->val != slow->val) return false; else { A = A->next; slow = slow->next; } } return true; }};
转载地址:http://asbb.baihongyu.com/