反转链表

反转一个单链表。

分析:
1.在原链表上操作，定义三个指针，front，middle，end
2.front用于middle指向它的父节点
3.middle用于改变当前元素的next指针
4.end用于链表断链后可以让middle继续往后操作

ListNode* reverseList(ListNode* head) {
    if(!head)return head;
    ListNode* tmp=(ListNode*)malloc(sizeof(ListNode));
    tmp->next=head;
    ListNode* front=tmp;
    ListNode* middle=front->next;
    ListNode* end=middle->next;
    while(end!=NULL){
        middle->next=front;
        front=middle;
        middle=end;
        end=end->next;
    }
    middle->next=front;
    head->next=NULL;
    return middle;
}

回文链表

请检查一个链表是否为回文链表。

分析:
1.定义一个slow慢指针(每次一步)与一个fast快指针(每次两步)
2.当fast到链表结尾是，slow则处于链的表中点位置
3.利用栈的特性来保存每次slow经过的节点，用于之后的比较

bool isPalindrome(ListNode* head) {
       if (!head || !head->next) return true;
       ListNode* slow=head;
       ListNode* fast=head;
       vector<int> stack;
       while(fast&&fast->next){
           stack.push_back(slow->val);
           slow=slow->next;  
           fast=fast->next->next;
       }
      if(fast)slow=slow->next;
       while(slow){
          if(slow->val!=stack.back()){
              return false;
          }else{
              slow=slow->next;
              stack.pop_back();
          }
       }
       return true;
}