回文链表 牛客网 程序员面试金典  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