Leetcode-234 回文链表

在这里插入图片描述

我的解法：使用栈，定义了len略微复杂，拿链表的后半部分和前半部分比较即可，没必要全部比较

/*** 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 head1=head;int len=0;while(head1!=null){len++;head1=head1.next;}Stack<Integer> s = new Stack<Integer>();int i=0;while(i<len/2){i++;s.push(head.val);head=head.next;}if(len%2==1){i++;head=head.next;}while(i<len){i++;if(head.val != s.pop()){return false;}else{head=head.next;}}return true;}
}

使用栈，和我想法类似，不定义len，所有元素全部入栈，出栈依次与头结点遍历元素相比较。

public boolean isPalindrome(ListNode head) {ListNode temp = head;Stack<Integer> stack = new Stack();//把链表节点的值存放到栈中while (temp != null) {stack.push(temp.val);temp = temp.next;}//然后再出栈while (head != null) {if (head.val != stack.pop()) {return false;}head = head.next;}return true;
}

反转后半部分链表（我应该想不到，又麻烦还要双指针…）

public boolean isPalindrome(ListNode head) {ListNode fast = head, slow = head;//通过快慢指针找到中点while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;}//如果fast不为空，说明链表的长度是奇数个if (fast != null) {slow = slow.next;}//反转后半部分链表slow = reverse(slow);fast = head;while (slow != null) {//然后比较，判断节点值是否相等if (fast.val != slow.val)return false;fast = fast.next;slow = slow.next;}return true;
}//反转链表
public ListNode reverse(ListNode head) {ListNode prev = null;while (head != null) {ListNode next = head.next;head.next = prev;prev = head;head = next;}return prev;
}作者：数据结构和算法
链接：https://leetcode.cn/problems/palindrome-linked-list/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。