回文链表 牛客网 程序员面试金典C++ Python

回文链表 牛客网 程序员面试金典  C++ Python

题目描述请编写一个函数，检查链表是否为回文。给定一个链表ListNode* pHead，请返回一个bool，代表链表是否为回文。测试样例：{1,2,3,2,1}返回：true{1,2,3,2,3}返回：false class Palindrome { public: // run:4ms memory:492k bool isPalindrome(ListNode* pHead) { if(NULL == pHead) return true; if(NULL == pHead->next) return true; if(NULL == pHead->next->next) if(pHead->val == pHead->next->val) return true; else return false; bool ret = true; ListNode* lastNode = NULL; ListNode* nextNode = pHead->next; ListNode* pSlow = pHead; ListNode* pFast = pHead; while(pFast && pFast->next){ pFast = pFast->next->next; pSlow->next = lastNode; lastNode = pSlow; pSlow = nextNode; nextNode = nextNode->next; } ListNode* lNode = lastNode; ListNode* nNode = pSlow; if (NULL == pFast) if (pSlow->val != lastNode->val) ret = false; else lastNode = lastNode->next; while(lastNode){ if (lastNode->val != nextNode->val) { ret = false; break; } lastNode = lastNode->next; nextNode = nextNode->next; } while(lNode){ ListNode* tmp = lNode->next; lNode->next = nNode; nNode = lNode; lNode = tmp; } return ret; } // run:5ms memory:600k bool isPalindrome2(ListNode* pHead) { if(NULL == pHead) return true; if(NULL == pHead->next) return true; if(NULL == pHead->next->next) if(pHead->val == pHead->next->val) return true; else return false; ListNode* lastNode = NULL; ListNode* nextNode = pHead->next; ListNode* pSlow = pHead; ListNode* pFast = pHead; while(pFast && pFast->next){ pFast = pFast->next->next; pSlow->next = lastNode; lastNode = pSlow; pSlow = nextNode; nextNode = nextNode->next; } if (NULL == pFast) if (pSlow->val != lastNode->val) return false; else lastNode = lastNode->next; while(lastNode){ if (lastNode->val != nextNode->val) return false; lastNode = lastNode->next; nextNode = nextNode->next; } return true; } // run:4ms memory:476k bool isPalindrome3(ListNode* pHead) { if(NULL == pHead) return true; if(NULL == pHead->next) return true; if(NULL == pHead->next->next) if(pHead->val == pHead->next->val) return true; else return false; ListNode* lastNode = NULL; ListNode* nextNode = pHead->next; ListNode* pSlow = pHead; ListNode* pFast = pHead; while(pFast && pFast->next){ pFast = pFast->next->next; pSlow->next = lastNode; lastNode = pSlow; pSlow = nextNode; nextNode = nextNode->next; } if (NULL == pFast){ if (pSlow->val != lastNode->val) return false; else{ lastNode = lastNode->next; while(lastNode){ if (lastNode->val != nextNode->val) return false; lastNode = lastNode->next; nextNode = nextNode->next; } } } if(NULL == pFast->next){ while(lastNode){ if (lastNode->val != nextNode->val) return false; lastNode = lastNode->next; nextNode = nextNode->next; } } return true; } };

Python

# class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Palindrome: # run:43ms memory:5732k def isPalindrome(self, pHead): if None == pHead: return True if None == pHead.next: return True if None == pHead.next.next: if pHead.val == pHead.next.val: return True else: return False ret = True lastNode = None nextNode = pHead pFast = pHead pSlow = pHead while pFast and pFast.next: pFast = pFast.next.next nextNode = pSlow.next pSlow.next = lastNode lastNode = pSlow pSlow = nextNode nextNode = nextNode.next lNode = lastNode nNode = pSlow if None == pFast: if pSlow.val != lastNode.val:ret = False else:lastNode = lastNode.next while lastNode and nextNode: if lastNode.val != nextNode.val: ret = False lastNode = lastNode.next nextNode = nextNode.next while lNode: tmp = lNode.next lNode.next = nNode nNode = lNode lNode = tmp return ret # run:34ms memory:5728k def isPalindrome2(self, pHead): if None == pHead: return True if None == pHead.next: return True if None == pHead.next.next: if pHead.val == pHead.next.val: return True else: return False lastNode = None nextNode = pHead pFast = pHead pSlow = pHead while pFast and pFast.next: pFast = pFast.next.next nextNode = pSlow.next pSlow.next = lastNode lastNode = pSlow pSlow = nextNode nextNode = nextNode.next if None == pFast: if pSlow.val != lastNode.val:return False else:lastNode = lastNode.next while lastNode: if lastNode.val != nextNode.val:return False lastNode = lastNode.next nextNode = nextNode.next return True

 

转载于:https://www.cnblogs.com/vercont/p/10210327.html

相关资源：JAVA上百实例源码以及开源项目