回文链表(C语言)

2024-07-11 03:30| 来源: 网络整理| 查看: 265

1.题目

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2 输出: false 示例 2:

输入: 1->2->2->1 输出: true 进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

思路

1.首先使用快慢双指针找到链表中点。 2.将链表后半段进行反转将反转后的后半段与链表前半段比较。

代码 /** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ bool isPalindrome(struct ListNode* head) { if(head==NULL) return true; struct ListNode *fast,*slow,*p,*q,*temp=NULL; fast=slow=head; while(fast->next && fast->next->next){ fast=fast->next->next; slow=slow->next; } slow=slow->next; while(slow!=NULL){ p=slow; slow=slow->next; p->next=temp; temp=p; } while(temp!=NULL){ if(temp->val!=head->val){ return false; } temp=temp->next; head=head->next; } return true; }

【本文地址】

公司简介

联系我们