lt.234-回文链表
[案例需求]
[思路分析一, 简单突破]
- 经过近四十道链表题的锤炼, 笔主深刻的体会到, 链表题目跟集合, 指针真的是关联性太强了!!!
- 对于链表类的题目, 如果你在尝试遍历集合(无论是普通的遍历, 还是使用快慢针形式的) 有一定困难的话, 那么使用集合或者数组存储链表结点或者结点的值, 来解决给定问题, 是一种非常简单直接的方法;
- 比如这道题, 鉴定一条链表是否是回文链表, 我们直接遍历来比较的话, 肯定是稍微有点难想的, 那么可以把链表的结点拆下来, 题目要求顺序(因为要判断是否符合回文), 我们就让他顺序, 然后通过对撞双指针的形式比较即可.
- 选择数组的话, 可行, 但是你得遍历完链表才能知道结点个数, 进而才能去初始化数组, 再去遍历链表存储结点, 太繁琐!
- 我们就选择集合, 使用可以随机访问的集合, 那么肯定就list了
- 题目思路:
-
- 遍历链表, 把链表值存入集合(直接把结点存入也是可行的)
-
- 然后对撞双指针, 相向遍历list, 比较是否相等, 不相等, 直接返回false即可;
[代码实现一, ]
/**
* 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) {
//对于这种遍历难解决的问题, 我们大可以交给集合, 数组
//全部放入数组(数组不知道大小, 干), 然后我双指针对撞遍历
//那我就放进list, 然后对撞遍历
ListNode temp = head;
List<Integer> list = new ArrayList<>();
while(temp != null){
list.add(temp.val);
temp = temp.next;
}
//
int size = list.size();
for(int i = 0; i < size; i++){
int left = i;
int right = size - i - 1;
if(list.get(left) != list.get(right)){
return false;
}
}
return true;
}
}
[思路分析二, 快慢指针 ]
- 找到前半部分链表的尾结点, 也就是整个链表中间结点的前一个结点, 先掌握求链表中间结点的写法吧: lt. 876. 链表的中间结点
- 反转后半部分链表, lt. 206 反转链表
- 判断是否回文
- 恢复链表
- 返回结果
/**
* 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. 获取中间结点
//2. 反转中间结点后面的链表
//3. 从头指针和从中间结点往后遍历并比较
//4. 恢复反转后的链表(再翻转一次)
//1. 获取中间结点
ListNode middleNode = getMiddleNode(head);
//2. 反转中结点后面的链表
ListNode behindMid = reverse(middleNode.next);
//3. 连接起来
//middleNode.next = behindMid;
//4. 比较结点
ListNode fromHead = head;
ListNode fromMid = behindMid;
boolean result = true;
while(result && fromMid!= null){
if(fromHead.val != fromMid.val) result = false;
fromHead = fromHead.next;
fromMid = fromMid.next;
}
return result;
}
public ListNode getMiddleNode(ListNode head){
ListNode fast = head;
ListNode slow = head;
while(fast.next != null && fast.next.next != null){
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
//反转链表
public ListNode reverse(ListNode head){
//递归出口
if(head == null || head.next == null)return head;
//递归入口
ListNode newHead = reverse(head.next);
//归来
head.next.next = head;
head.next = null;
return newHead;
}
}
[思路分析三, 巧妙的解法, ]
- 题解参见: 点我
/**
* 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) {
if(head == null || head.next == null) {
return true;
}
ListNode slow = head, fast = head;
ListNode pre = head, prepre = null;
while(fast != null && fast.next != null) {
pre = slow;
slow = slow.next;
fast = fast.next.next;
pre.next = prepre;
prepre = pre;
}
if(fast != null) {
slow = slow.next;
}
while(pre != null && slow != null) {
if(pre.val != slow.val) {
return false;
}
pre = pre.next;
slow = slow.next;
}
return true;
}
}
[思路分析三, 递归法]
// 待补充
