Given a singly linked list, determine if it is a palindrome.

Could you do it in O(n) time and O(1) space?

1. 必须做的第一个步骤就是判断输入链表是否为空，或者只有一个元素。如果为空或者只有一个元素，则此链表为回文链表返回true。
2. 使用快慢指针，找到链表中点。慢指针一次走一步，快指针一次走两步。
3. 根据找到的链表中点，反转后半部分的链表的所有值，并与整体单链表的值从头依次比对，有一个值不同，则不是回文链表，否则为回文链表。 如输入单链表：[1, 2, 3, 2, 1]

Language:C

```/**
* struct ListNode {
*     int val;
*     struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode* pre = (struct ListNode *)malloc(sizeof(struct ListNode));
struct ListNode* next = (struct ListNode *)malloc(sizeof(struct ListNode));
pre=NULL;
next=NULL;
}
return pre;
}

struct ListNode* slow = (struct ListNode *)malloc(sizeof(struct ListNode));
struct ListNode* fast = (struct ListNode *)malloc(sizeof(struct ListNode));
return true;
}
while(fast->next && fast->next->next){
slow = slow->next;
fast = fast->next->next;
}
slow = reverseList(slow->next);
while(slow){
return false;
}
slow = slow->next;
}
return true;
}```

Language:cpp

```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
return true;
}
while(fast->next && fast->next->next){
slow = slow->next;
fast = fast->next->next;
}
slow = reverseList(slow->next);
while(slow){
return false;
}
slow = slow->next;
}
return true;
}
ListNode* pre = NULL;
ListNode* next = NULL;
}
return pre;
}
};```

0 条评论

## 相关文章

### 链表逆序

1.构造5个节点a,b,c,d,e,并对它们进行初始化； 2.将a,b,c,d,e,5个节点连接在一起

1004

Add Two Numbers Total Accepted: 160702 Total Submissions: 664770 Difficulty: Med...

2495

You are given two non-empty linked lists representing two non-negative integers....

891

### Leetcode 21 Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should b...

2109

872

### Leetcode 148 SortList

Sort a linked list in O(n log n) time using constant space complexity. 链表排序，n...

1997

### Leetcode 82 Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leavi...

2025

1052

2207

### LeetCode 2 & 455 Add Two Numbers I&II

You are given two non-empty linked lists representing two non-negative integers....

900