Leetcode题库面试题 02.06. 回文链表

文章目录

• 思路
• 代码

思路

核心思想：
利用递归以达到从单向链表尾部开始遍历，直至链表头部的效果

第一步：
递归，使得p1指向链表尾部

第二步：
比较p1与p2(p2从链表头部开始遍历)的val，若两者不等，则ret=0

代码

int ret=1;

struct ListNode* f(struct ListNode* head,struct ListNode* p1,struct ListNode* p2){
    if(p1->next!=NULL) p2=f(head,p1->next,p2);
    if(p1->val!=p2->val){
        ret=0;
    }
    return p2->next;
}

bool isPalindrome(struct ListNode* head){
    struct ListNode *p1=head,*p2=head;
    int temp;
    if(head!=NULL) p2=f(head,p1,p2);
    temp=ret;
    //ret归1，以便下一次函数调用
    ret=1;
    return temp==1;
}