430 lines
11 KiB
Markdown
Executable File
430 lines
11 KiB
Markdown
Executable File
* [做项目（多个C++、Java、Go、测开、前端项目）](https://www.programmercarl.com/other/kstar.html)
|
||
* [刷算法（两个月高强度学算法）](https://www.programmercarl.com/xunlian/xunlianying.html)
|
||
* [背八股（40天挑战高频面试题）](https://www.programmercarl.com/xunlian/bagu.html)
|
||
|
||
|
||
# 234.回文链表
|
||
|
||
[力扣题目链接](https://leetcode.cn/problems/palindrome-linked-list/)
|
||
|
||
请判断一个链表是否为回文链表。
|
||
|
||
示例 1:
|
||
* 输入: 1->2
|
||
* 输出: false
|
||
|
||
示例 2:
|
||
* 输入: 1->2->2->1
|
||
* 输出: true
|
||
|
||
|
||
## 思路
|
||
|
||
### 数组模拟
|
||
|
||
最直接的想法，就是把链表装成数组，然后再判断是否回文。
|
||
|
||
代码也比较简单。如下：
|
||
|
||
```CPP
|
||
class Solution {
|
||
public:
|
||
bool isPalindrome(ListNode* head) {
|
||
vector<int> vec;
|
||
ListNode* cur = head;
|
||
while (cur) {
|
||
vec.push_back(cur->val);
|
||
cur = cur->next;
|
||
}
|
||
// 比较数组回文
|
||
for (int i = 0, j = vec.size() - 1; i < j; i++, j--) {
|
||
if (vec[i] != vec[j]) return false;
|
||
}
|
||
return true;
|
||
}
|
||
};
|
||
```
|
||
|
||
上面代码可以在优化，就是先求出链表长度，然后给定vector的初始长度，这样避免vector每次添加节点重新开辟空间
|
||
|
||
```CPP
|
||
class Solution {
|
||
public:
|
||
bool isPalindrome(ListNode* head) {
|
||
|
||
ListNode* cur = head;
|
||
int length = 0;
|
||
while (cur) {
|
||
length++;
|
||
cur = cur->next;
|
||
}
|
||
vector<int> vec(length, 0); // 给定vector的初始长度，这样避免vector每次添加节点重新开辟空间
|
||
cur = head;
|
||
int index = 0;
|
||
while (cur) {
|
||
vec[index++] = cur->val;
|
||
cur = cur->next;
|
||
}
|
||
// 比较数组回文
|
||
for (int i = 0, j = vec.size() - 1; i < j; i++, j--) {
|
||
if (vec[i] != vec[j]) return false;
|
||
}
|
||
return true;
|
||
}
|
||
};
|
||
|
||
```
|
||
|
||
### 反转后半部分链表
|
||
|
||
分为如下几步：
|
||
|
||
* 用快慢指针，快指针有两步，慢指针走一步，快指针遇到终止位置时，慢指针就在链表中间位置
|
||
* 同时用pre记录慢指针指向节点的前一个节点，用来分割链表
|
||
* 将链表分为前后均等两部分，如果链表长度是奇数，那么后半部分多一个节点
|
||
* 将后半部分反转 ，得cur2，前半部分为cur1
|
||
* 按照cur1的长度，一次比较cur1和cur2的节点数值
|
||
|
||
如图所示：
|
||
|
||
<img src='https://file1.kamacoder.com/i/algo/234.回文链表.png' width=600> </img></div>
|
||
|
||
代码如下：
|
||
|
||
```CPP
|
||
class Solution {
|
||
public:
|
||
bool isPalindrome(ListNode* head) {
|
||
if (head == nullptr || head->next == nullptr) return true;
|
||
ListNode* slow = head; // 慢指针，找到链表中间分位置，作为分割
|
||
ListNode* fast = head;
|
||
ListNode* pre = head; // 记录慢指针的前一个节点，用来分割链表
|
||
while (fast && fast->next) {
|
||
pre = slow;
|
||
slow = slow->next;
|
||
fast = fast->next->next;
|
||
}
|
||
pre->next = nullptr; // 分割链表
|
||
|
||
ListNode* cur1 = head; // 前半部分
|
||
ListNode* cur2 = reverseList(slow); // 反转后半部分，总链表长度如果是奇数，cur2比cur1多一个节点
|
||
|
||
// 开始两个链表的比较
|
||
while (cur1) {
|
||
if (cur1->val != cur2->val) return false;
|
||
cur1 = cur1->next;
|
||
cur2 = cur2->next;
|
||
}
|
||
return true;
|
||
}
|
||
// 反转链表
|
||
ListNode* reverseList(ListNode* head) {
|
||
ListNode* temp; // 保存cur的下一个节点
|
||
ListNode* cur = head;
|
||
ListNode* pre = nullptr;
|
||
while(cur) {
|
||
temp = cur->next; // 保存一下 cur的下一个节点，因为接下来要改变cur->next
|
||
cur->next = pre; // 翻转操作
|
||
// 更新pre 和 cur指针
|
||
pre = cur;
|
||
cur = temp;
|
||
}
|
||
return pre;
|
||
}
|
||
};
|
||
```
|
||
|
||
|
||
## 其他语言版本
|
||
|
||
### Java
|
||
|
||
```java
|
||
// 方法一，使用数组
|
||
class Solution {
|
||
public boolean isPalindrome(ListNode head) {
|
||
int len = 0;
|
||
// 统计链表长度
|
||
ListNode cur = head;
|
||
while (cur != null) {
|
||
len++;
|
||
cur = cur.next;
|
||
}
|
||
cur = head;
|
||
int[] res = new int[len];
|
||
// 将元素加到数组之中
|
||
for (int i = 0; i < res.length; i++){
|
||
res[i] = cur.val;
|
||
cur = cur.next;
|
||
}
|
||
// 比较回文
|
||
for (int i = 0, j = len - 1; i < j; i++, j--){
|
||
if (res[i] != res[j]){
|
||
return false;
|
||
}
|
||
}
|
||
return true;
|
||
}
|
||
}
|
||
|
||
// 方法二，快慢指针
|
||
class Solution {
|
||
public boolean isPalindrome(ListNode head) {
|
||
// 如果为空或者仅有一个节点，返回true
|
||
if (head == null && head.next == null) return true;
|
||
ListNode slow = head;
|
||
ListNode fast = head;
|
||
ListNode pre = head;
|
||
while (fast != null && fast.next != null){
|
||
pre = slow; // 记录slow的前一个结点
|
||
slow = slow.next;
|
||
fast = fast.next.next;
|
||
}
|
||
pre.next = null; // 分割两个链表
|
||
|
||
// 前半部分
|
||
ListNode cur1 = head;
|
||
// 后半部分。这里使用了反转链表
|
||
ListNode cur2 = reverseList(slow);
|
||
|
||
while (cur1 != null){
|
||
if (cur1.val != cur2.val) return false;
|
||
|
||
// 注意要移动两个结点
|
||
cur1 = cur1.next;
|
||
cur2 = cur2.next;
|
||
}
|
||
return true;
|
||
}
|
||
ListNode reverseList(ListNode head){
|
||
// 反转链表
|
||
ListNode tmp = null;
|
||
ListNode pre = null;
|
||
while (head != null){
|
||
tmp = head.next;
|
||
head.next = pre;
|
||
pre = head;
|
||
head = tmp;
|
||
}
|
||
return pre;
|
||
}
|
||
}
|
||
```
|
||
|
||
### Python
|
||
|
||
```python
|
||
#数组模拟
|
||
class Solution:
|
||
def isPalindrome(self, head: Optional[ListNode]) -> bool:
|
||
list=[]
|
||
while head:
|
||
list.append(head.val)
|
||
head=head.next
|
||
l,r=0, len(list)-1
|
||
while l<=r:
|
||
if list[l]!=list[r]:
|
||
return False
|
||
l+=1
|
||
r-=1
|
||
return True
|
||
|
||
#反转后半部分链表
|
||
class Solution:
|
||
def isPalindrome(self, head: Optional[ListNode]) -> bool:
|
||
fast = slow = head
|
||
|
||
# find mid point which including (first) mid point into the first half linked list
|
||
while fast and fast.next:
|
||
fast = fast.next.next
|
||
slow = slow.next
|
||
node = None
|
||
|
||
# reverse second half linked list
|
||
while slow:
|
||
slow.next, slow, node = node, slow.next, slow
|
||
|
||
# compare reversed and original half; must maintain reversed linked list is shorter than 1st half
|
||
while node:
|
||
if node.val != head.val:
|
||
return False
|
||
node = node.next
|
||
head = head.next
|
||
return True
|
||
```
|
||
|
||
### Go
|
||
|
||
```go
|
||
/**
|
||
* Definition for singly-linked list.
|
||
* type ListNode struct {
|
||
* Val int
|
||
* Next *ListNode
|
||
* }
|
||
*/
|
||
//方法一，使用数组
|
||
func isPalindrome(head *ListNode) bool{
|
||
//计算切片长度，避免切片频繁扩容
|
||
cur,ln:=head,0
|
||
for cur!=nil{
|
||
ln++
|
||
cur=cur.Next
|
||
}
|
||
nums:=make([]int,ln)
|
||
index:=0
|
||
for head!=nil{
|
||
nums[index]=head.Val
|
||
index++
|
||
head=head.Next
|
||
}
|
||
//比较回文切片
|
||
for i,j:=0,ln-1;i<=j;i,j=i+1,j-1{
|
||
if nums[i]!=nums[j]{return false}
|
||
}
|
||
return true
|
||
}
|
||
|
||
// 方法二，快慢指针
|
||
func isPalindrome(head *ListNode) bool {
|
||
if head==nil&&head.Next==nil{return true}
|
||
//慢指针，找到链表中间分位置，作为分割
|
||
slow:=head
|
||
fast:=head
|
||
//记录慢指针的前一个节点，用来分割链表
|
||
pre:=head
|
||
for fast!=nil && fast.Next!=nil{
|
||
pre=slow
|
||
slow=slow.Next
|
||
fast=fast.Next.Next
|
||
}
|
||
//分割链表
|
||
pre.Next=nil
|
||
//前半部分
|
||
cur1:=head
|
||
//反转后半部分，总链表长度如果是奇数，cur2比cur1多一个节点
|
||
cur2:=ReverseList(slow)
|
||
|
||
//开始两个链表的比较
|
||
for cur1!=nil{
|
||
if cur1.Val!=cur2.Val{return false}
|
||
cur1=cur1.Next
|
||
cur2=cur2.Next
|
||
}
|
||
return true
|
||
}
|
||
//反转链表
|
||
func ReverseList(head *ListNode) *ListNode{
|
||
var pre *ListNode
|
||
cur:=head
|
||
for cur!=nil{
|
||
tmp:=cur.Next
|
||
cur.Next=pre
|
||
pre=cur
|
||
cur=tmp
|
||
}
|
||
return pre
|
||
}
|
||
```
|
||
|
||
### JavaScript
|
||
|
||
```js
|
||
var isPalindrome = function(head) {
|
||
const reverseList = head => {// 反转链表
|
||
let temp = null;
|
||
let pre = null;
|
||
while(head != null){
|
||
temp = head.next;
|
||
head.next = pre;
|
||
pre = head;
|
||
head = temp;
|
||
}
|
||
return pre;
|
||
}
|
||
// 如果为空或者仅有一个节点，返回true
|
||
if(!head && !head.next) return true;
|
||
let slow = head;
|
||
let fast = head;
|
||
let pre = head;
|
||
while(fast != null && fast.next != null){
|
||
pre = slow; // 记录slow的前一个结点
|
||
slow = slow.next;
|
||
fast = fast.next.next;
|
||
}
|
||
pre.next = null; // 分割两个链表
|
||
// 前半部分
|
||
let cur1 = head;
|
||
// 后半部分。这里使用了反转链表
|
||
let cur2 = reverseList(slow);
|
||
while(cur1 != null){
|
||
if(cur1.val != cur2.val) return false;
|
||
// 注意要移动两个结点
|
||
cur1 = cur1.next;
|
||
cur2 = cur2.next;
|
||
}
|
||
return true;
|
||
};
|
||
```
|
||
|
||
### TypeScript
|
||
|
||
> 数组模拟
|
||
|
||
```typescript
|
||
function isPalindrome(head: ListNode | null): boolean {
|
||
const helperArr: number[] = [];
|
||
let curNode: ListNode | null = head;
|
||
while (curNode !== null) {
|
||
helperArr.push(curNode.val);
|
||
curNode = curNode.next;
|
||
}
|
||
let left: number = 0,
|
||
right: number = helperArr.length - 1;
|
||
while (left < right) {
|
||
if (helperArr[left++] !== helperArr[right--]) return false;
|
||
}
|
||
return true;
|
||
};
|
||
```
|
||
|
||
> 反转后半部分链表
|
||
|
||
```typescript
|
||
function isPalindrome(head: ListNode | null): boolean {
|
||
if (head === null || head.next === null) return true;
|
||
let fastNode: ListNode | null = head,
|
||
slowNode: ListNode = head,
|
||
preNode: ListNode = head;
|
||
while (fastNode !== null && fastNode.next !== null) {
|
||
preNode = slowNode;
|
||
slowNode = slowNode.next!;
|
||
fastNode = fastNode.next.next;
|
||
}
|
||
preNode.next = null;
|
||
let cur1: ListNode | null = head;
|
||
let cur2: ListNode | null = reverseList(slowNode);
|
||
while (cur1 !== null) {
|
||
if (cur1.val !== cur2!.val) return false;
|
||
cur1 = cur1.next;
|
||
cur2 = cur2!.next;
|
||
}
|
||
return true;
|
||
};
|
||
function reverseList(head: ListNode | null): ListNode | null {
|
||
let curNode: ListNode | null = head,
|
||
preNode: ListNode | null = null;
|
||
while (curNode !== null) {
|
||
let tempNode: ListNode | null = curNode.next;
|
||
curNode.next = preNode;
|
||
preNode = curNode;
|
||
curNode = tempNode;
|
||
}
|
||
return preNode;
|
||
}
|
||
```
|
||
|
||
|
||
|
||
|