运用反转链表的思想实现力扣题

​

文章目录

• 从尾到头打印链表
• 回文链表

从尾到头打印链表

link.

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：

输入：head = [1,3,2] 输出：[2,3,1]

int* reversePrint(struct ListNode* head, int* returnSize)
{
    if(head==NULL)
    {
        *returnSize=0;
        return NULL;
    }
//先反转链表
struct ListNode*newhead=NULL,*cur=head,*next=cur->next;
int a=0;
while(cur)
{
    a++;
    cur->next=newhead;
    newhead=cur;
    cur=next;
    if(next)
    next=next->next;
}
int *ret=(int *)malloc(sizeof(int)*a);//开辟数组来接收newnode的值
for(int i=0;i<a;i++)
{
    ret[i]=newhead->val;
    newhead=newhead->next;
}
*returnSize=a;
return ret;
}

回文链表

link.

给定一个链表的 头节点 head ，请判断其是否为回文链表。

如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

示例 1：

输入: head = [1,2,3,3,2,1] 输出: true

示例 2：

输入: head = [1,2] 输出: false

提示：

链表 L 的长度范围为 [1, 105]
0 <= node.val <= 9

思路

1221，我们先找到中间节点，然后再把mid进行后面链表进行反转 ，再一一比较，如果一条到空都相同则为真，有一个不同就是假
如1221，就是12和1221进行比较，都相同
或则12321，12321和123进行比较

struct ListNode*midnode(struct ListNode*head)//找中间节点
{
    struct ListNode*fast=head,*slow=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
    }
    return slow;
}

struct ListNode* reverse(struct ListNode*head)//反转链表
{
    
    struct ListNode*newhead=NULL;
    struct ListNode*cur=head;
    struct ListNode*next=cur->next;
    while(cur)
    {
        cur->next=newhead;
        newhead=cur;
        cur=next;
        if(next)
        next=next->next;
    }
return newhead;
}

bool isPalindrome(struct ListNode* head)
{
if(head==NULL)
{
    return true;
}
struct ListNode*phead=head;
struct ListNode*mid=midnode(phead);
struct ListNode*now=reverse(mid);
while(head&&now)
{
    if(head->val!=now->val)
    {
        return false;
    }
    head=head->next;
    now=now->next;
}
return true;
}