Letcode--反转链表+回文链表

  ok小伙伴们，今天给大家带来关于链表的算法题目。首先学习一下反转链表，大家先看题目：

  这道题目比较简单，所以先给大家看一下代码：

ListNode* reverseList(ListNode* head) {
        if(!head){
            return nullptr;
        }
        ListNode *pre=nullptr,*cur=head,*nextcur;
        while(cur){
            nextcur=cur->next;
            cur->next=pre;
            pre=cur;
            cur=nextcur;
        }
        return pre;
    }

  在代码中，我们使用了pre、cur、nextcur指针。pre用于记录反转后应指向的节点（初始为nullptr），cur指向当前节点， nextcur为cur未反转所指向的下一个节点，用于链表的遍历。

  最后链表遍历完成后，cur为nullptr，pre为反转后的头节点，返回pre即可。

  在此基础上，我们引入新的题目：回文链表，大家先阅读题目：

  先给大家举个例子，如链表节点为1->2->3->2->1，从前向后和从后向前遍历结果相同，那么它就算回文链表。如果链表节点为1->2，从前向后遍历顺序为12，从后向前遍历顺序为21，结果不同，那么就不是回文链表。

   对于此例，我们采用快慢指针方法，慢指针一次走一步，快指针一次走两步。（看过我之前文章的小伙伴应该知道我们用快慢指针解决过链表是否有环的问题）fast指针从1出发，走到3，走到2，走到nullptr。（节点个数为偶数才会走到nullptr）当fast走到nullptr时，slow走到了3（第二个），如果我们此时将slow及其之后的链表反转，并将fast移动到原先的head，并且fast速度恢复为1，再对两条链表进行遍历（循环结束条件为slow为nullptr或者fast为nullptr），分别比较节点数据是否相同即可得出最终答案。

     对于奇数个节点，fast从1走到3，走到1。slow此时走到3。此时将slow再继续下移一步，移动到2，再将slow及其以后的链表反转，并将fast移动到原先的head，并且fast速度恢复为1，再对两条链表进行遍历（循环结束条件为slow为nullptr），再对两条链表进行遍历，分别比较节点数据是否相同即可得出最终答案。

    据此我们给出代码：

bool isPalindrome(ListNode* head) {
        if(!head->next){
            return 1;
        }
        ListNode *fast=head,*slow=head;
        int flag=1;
        while(fast->next){
            fast=fast->next->next;
            slow=slow->next;
            if(!fast){
                flag=0;
                break;
            }
        }
        if(flag){
            slow=slow->next;
        }
        fast=head;
        ListNode *pre=nullptr,*cur=slow,*nextcur;
        while(cur){
            nextcur=cur->next;
            cur->next=pre;
            pre=cur;
            cur=nextcur;
        }
        slow=pre;
        while(slow){
            if(fast->val!=slow->val){
                return 0;
            }
            slow=slow->next;
            fast=fast->next;
        }
        return 1;
    }

    今天的文章就写到这里，希望大家多多支持，有疑问的地方欢迎在评论区讨论！谢谢大家！