文章目录
从尾到头打印链表
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;
}