当前位置:网站首页>Interview question 02.06 Palindrome linked list
Interview question 02.06 Palindrome linked list
2022-06-11 07:07:00 【Not coriander】
Write a function , Check whether the input list is palindromic .
Example 1:
Input : 1->2
Output : false
Example 2:
Input : 1->2->2->1
Output : true
Advanced :
Can you use O(n) Time complexity and O(1) Space complexity to solve this problem ?
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
class Solution {
public:
ListNode *head2;
bool f(ListNode*p){
if(p==NULL){
return true;
}
if(f(p->next)==false){
return false;
}
if(p->val!=head2->val)return false;
head2=head2->next;
return true;
}
bool isPalindrome(ListNode* head) {
head2=head;
return f(head);
}
};
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
class Solution {
public:
// Reverse a linked list
ListNode* reverseList(ListNode* head) {
if(head==NULL||head->next==NULL){
return head;
}
ListNode* p=reverseList(head->next);
head->next->next=head;
head->next=NULL;
return p;
}
bool isPalindrome(ListNode* head) {
ListNode *node1=new ListNode(0,head);
ListNode *node2=new ListNode(0,head);
while(node2->next){
node1=node1->next;
// cout<<node1->val<<" ";
node2=node2->next;
if(node2->next){
node2=node2->next;
}
else{
break;
}
}
node1=reverseList(node1->next);
node2=head;
// cout<<endl<<node1->val<<" "<<node2->val<<endl;
while(node1){
if(node1->val!=node2->val){
return false;
}
node1=node1->next;
node2=node2->next;
}
return true;
}
};
边栏推荐
- Aircraft war from scratch (II) simple development
- Object. Specific implementation and difference between create() and new
- Summary of string processing skills III
- Latex various arrows / arrows with text labels / variable length arrows
- 模块化笔记
- webserver
- Saltstack deployment ZABBIX state file writing
- Aircraft battle from scratch (III) flight between player aircraft and enemy aircraft
- Esp32 learning notes (49) - esp-wifi-mesh interface use
- 1266_FreeRTOS调度器启动代码实现分析
猜你喜欢

Common troubleshooting tools and analysis artifacts are worth collecting
![[deploy private warehouse based on harbor] 3 deploy harbor](/img/cd/be68a430e86b4b23ad93b42a338f00.jpg)
[deploy private warehouse based on harbor] 3 deploy harbor

品牌定位个性六种形态及结论的重大意义

迅为干货 |瑞芯微RK3568开发板TFTP&NFS烧写(上)

Nodejs database (Part 2)

Object. Specific implementation and difference between create() and new

Saltstack deployment LNMP

During unity panoramic roaming, AWSD is used to control lens movement, EQ is used to control lens lifting, and the right mouse button is used to control lens rotation.

Analysis of key points and difficulties of ES6 promise source code
![[matlab WSN communication] a_ Star improved leach multi hop transmission protocol [including source code phase 487]](/img/fd/53776b550390752282cd8797193436.png)
[matlab WSN communication] a_ Star improved leach multi hop transmission protocol [including source code phase 487]
随机推荐
Aircraft battle from scratch (III) flight between player aircraft and enemy aircraft
The meaning and research significance of mathematical methodology
数学方法论的含义和研究意义
Difference between byte and bit
Practice: how to reasonably design functions to solve practical problems in software development (I)
Atomicinteger atomic operation class
Object. Specific implementation and difference between create() and new
During unity panoramic roaming, AWSD is used to control lens movement, EQ is used to control lens lifting, and the right mouse button is used to control lens rotation.
Promise. All capture error
Detailed explanation of mutationobserver
Listen to the left width of the browser to calculate the distance
Leetcode-104. Maximum Depth of Binary Tree
Luogu p1091 chorus formation (longest ascending subsequence)
Summary of string processing skills II
Comparison of DOM tags of wechat applet development (native and uniapp)
matplotlib的cmap
Open source cartoon server mango
Interview question 17.08 Circus tower
Shangtang technology has actively resumed work and will vigorously invest in the capacity and deployment of the digital sentry
Notice on organizing the application for the first edition of Ningbo key software in 2022