回文链表的判断

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        // 单节点返回true
        if(!head -> next) return true;
        //先遍历一遍获得中心节点
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast && fast->next){
            fast = fast->next->next;
            slow = slow->next;
        };
        //如果fast->next存在,则总数pls slow是后链的第一个节点
        //如果fast -> next不存在,则总数odd slow 的下一个节点是后链的第一个节点
        //后链只可能比前链更少
        if(fast) slow = slow->next; //修正后链位置
        //然后将后链翻转
        ListNode* next = slow -> next;
        slow -> next = nullptr; //取消slow的后继节点,作为最后比较遍历的判断条件
        ListNode* temp = next;//此时slow -> next(temp)
        while(next){
            //temp后移 slow -> next -> temp(null)
            temp = temp -> next;
            next -> next = slow;
            slow = next;
            next = temp;
        }
        //最后得到的右链指针是slow
        while(slow){
            if(head->val!= slow->val)  return false;
            head = head->next;
            slow = slow->next;
        }
        return true;
        //遍历是否两个链相等
    }
};

链表的反转

void reverseString(vector<char>& s) {
    int i,j;
    char temp;
    for (i = 0,j = s.size() -1; i < s.size() / 2; i++,j--) {
        temp = s[i];
        s[i] = s[j];
        s[j] = temp;
    }
}