题目描述
思路1：将值复制到数组中然后使用双指针
- 计算链表的长度
- 创建等长的数组
- 将链表中的数依次放入数组中
- 使用左右指针判断链表是否是回文链表
时间复杂度：O(n)
空间复杂度：O(n)
思路2：快慢指针+反转链表
- 用快慢指针，快指针走两步，慢指针走一步，快指针遇到终止位置时，慢指针就在链表中间位置
- 同时用pre记录慢指针指向节点的前一个节点，用来分割链表
- 将链表分为前后均等两部分，如果链表长度是奇数，那么后半部分多一个节点
- 将后半部分翻转，得到cur2，前部分为cur1
- 按照cur1的长度，依次比较cur1和cur2的节点数值
方法一：对于思路1
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
ListNode p = head;
int length = 0;
List<Integer> list = new ArrayList<>();
int index = 0;
// 计算链表的长度,并且将链表的值依次存入链表中
while (p != null) {
list.add(p.val);
p = p.next;
index ++;
}
// 使用左右指针,判断链表是否是回文链表
int left = 0, right = list.size() - 1;
for (;left <= right; left ++, right--) {
if (list.get(left) != list.get(right)) {
return false;
}
}
return true;
}
}
方法二：对应思路2
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
// 1. 链表如果为空或者仅有一个节点，返回true
if (head == null && head.next == null) return true;
// 2. 定义快慢指针
ListNode slow = head;
ListNode fast = head;
ListNode pre = head;
while (fast != null && fast.next != null) {
// pre指针记录slow的前一个节点
pre = slow;
// fast指针一次走两步
fast = fast.next.next;
// slow指针一次走一步
slow = slow.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;
}
/**
反转链表的代码
*/
private ListNode reverseList(ListNode head) {
ListNode curNode = head;
ListNode preNode = null;
ListNode nextNode;
while (curNode != null) {
nextNode = curNode.next;
curNode.next = preNode;
preNode = curNode;
curNode = nextNode;
}
return preNode;
}
}