LeetCode 234.回文链表

234.回文链表

请判断一个链表是否为回文链表。

Solution1：

//获得链表长度
int getListLength(ListNode* head){
    int len = 0;
    while(head){
        head = head->next;
        len++;
    }
    return len;
}
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode* head1 = head;
        int listlen = getListLength(head1);
        if(listlen <= 1) return true;
        int mid = listlen/2;
        std::stack<int> s;
        while(mid && head){
            s.push(head->val);
            head = head->next;
            mid--;
        }
        if(listlen%2 != 0){
            head = head->next;
        }
        while(head){
            if(head->val != s.top()){
               return false; 
            }
            s.pop();
            head = head->next;
        }
        return true;
    }
};

思路:

借助stack。

将mid之前的元素值都push进stack中，然后到mid之后，将每个元素与栈顶值比较。不相等退出，相等继续下一轮。

---

Solution2：

//获得链表长度
int getListLength(ListNode* head){
    int len = 0;
    while(head){
        head = head->next;
        len++;
    }
    return len;
}

//根据位置与所给链表，向后移动position步。
ListNode* getNodeByPosition(ListNode* head,int position){
    while(position>0){
        head = head->next;
        position--;
    }
    return head;
}

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        //存储头结点。
        ListNode* first = head;
        ListNode* head1 = head;
        int listlen = getListLength(head);
        int midposition = listlen/2;
        //如果链表长度<=1，直接返回true;
        if(listlen <= 1) return true;
        //到达需要翻转的长度，对于偶数，为（listlen/2）+1，对于奇数，为listlen/2;
        ListNode* mid = getNodeByPosition(head1,midposition);
        //翻转mid之后的指针。
        ListNode * newHead = NULL;
        int position = listlen-midposition;
        while(mid && position){
            ListNode* next = mid->next;
            mid->next = newHead;
            newHead = mid;
            mid = next;
            position--;
        }
        //将翻转之后的链表与开头的链表的内容比较，向后比较listlen/2;
        //如果是偶数，则元素都会比较到，如果是奇数，最后一个元素不会比较到。他在原来的链表中就处于中心位置，不必比较。
        while(first && newHead && midposition){
            //只要不相等，就为false;
            if(first->val != newHead->val) return false;
            first = first->next;
            newHead = newHead->next;
            midposition--;
        }
        return true;
    }
};

思路：

将链表的后半段翻转，从翻转位置开始与从头结点开始，依次比较（listlen/2次）。