leetcode 234. 回文链表

leetcode

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

1. 快慢指针

class Solution {
public:
    bool isPalindrome(ListNode* head) {

        ListNode *quickNode = head; // 快指针，决定着只遍历链表的一半部分
        ListNode *previousNode = NULL;
        ListNode *currentNode = head;
        // 1. 翻转链表的前半部分
        while ( quickNode && quickNode -> next ) {
            
            quickNode = quickNode -> next -> next;
            ListNode *temp = currentNode -> next;
            currentNode -> next = previousNode;
            previousNode = currentNode;
            currentNode = temp;
        }
        if ( quickNode ) {
            
            // 当链表个数为奇数时，此时 quickNode 指向最后一个节点，current 指向中心点
            // 需要把 currentNode 往后指一位才能开始比较
            currentNode = currentNode -> next;
        }
        // 此时 previousNode 指向的链表为前半部分的翻转结果，如果是回文链表的话，则 previousNode 和 currentNode 接下来指向的会一摸一样
        /*
          1 -> 2 -> 3 -> 2 -> 1
          
          2 -> 1 -> 3 -> 2 -> 1
          ^              ^
     previousNode   currentNode
         */
        // 2. 开始遍历比较
        while ( previousNode && currentNode ) {
            
            if ( currentNode -> val != previousNode -> val ) {
                
                return false;
            }
            
            currentNode = currentNode -> next;
            previousNode = previousNode -> next;
        }
        
        return true;
    }
};

2. 栈

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        
        std::stack<ListNode *> stack;
        ListNode *quickNode = head; // 快指针，决定着只遍历链表的一半部分
        ListNode *currentNode = head;
        while ( quickNode && quickNode -> next ) {
            
            if ( currentNode ) {
                
                stack.push( currentNode );
            }
            
            currentNode = currentNode -> next;
            quickNode = quickNode -> next -> next;
        }
        if ( quickNode ) {
            
            currentNode = currentNode -> next;
        }
        
        while ( currentNode ) {
            
            if ( stack.empty() || !stack.top() || currentNode -> val != stack.top() -> val ) {
                
                return false;
            }
            
            currentNode = currentNode -> next;
            stack.pop();
        }
        
        if ( !stack.empty() ) {
            
            return false;
        }
        
        return true;
    }
};

3. 数组
   核心思想：将链表遍历一遍转换为数组，双指针指向数组头尾依次向内遍历