江苏元鼎建设工程有限公司网站,校园在线网站怎么做,自己创建app,江苏金地建设工程有限公司网站回文链表判定
给你一个单链表的头节点 head #xff0c;请你判断该链表是否为回文链表。如果是#xff0c;返回 true #xff1b;否则#xff0c;返回 false 。
方法一#xff1a;栈反转对比法
解题思路#xff1a;找到中间节点后用栈辅助反转对比 解题方法#xff1…回文链表判定
给你一个单链表的头节点 head 请你判断该链表是否为回文链表。如果是返回 true 否则返回 false 。
方法一栈反转对比法
解题思路找到中间节点后用栈辅助反转对比 解题方法 找到链表的中间节点并判断奇数还是偶数 头结点到中间节点前的节点入栈偶数从中间节点开始和栈内元素进行比较 奇数从中间节点后面的节点开始和栈内元素进行比较 若比较到最后一个节点都相等该链表为回文链表栈空或比较到最后一个节点 时间复杂度O(n) 空间复杂度O(n)
import java.util.List;
import java.util.Stack;import javax.management.ListenerNotFoundException;/*** 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 static boolean isPalindrome(ListNode head) {/*** head - 1 - 2 - 2 - 1 - null* head - 1 - 2 - 1 - null* 找到链表的中间节点并判断奇数还是偶数* 头结点到中间节点的节点入栈偶数从中间节点开始和栈内元素进行比较* 奇数从中间节点后面的节点开始和栈内元素进行比较* 若比较到最后一个节点都相当该链表为回文链表栈空或比较到最后一个节点*/if(head null){return false;}ListNode dummy new ListNode(-1);dummy.nexthead;ListNode slowdummy;ListNode fastdummy;ListNode midNodenull;Boolean isEventtrue;while (fast.next!null){slowslow.next;if(fast.next.next!null) {fast fast.next.next;} else{fastfast.next;isEventfalse;}}midNode isEvent ? slow.next : slow;StackListNode stacknew Stack();ListNode pdummy.next;while(p!midNode){stack.push(p);pp.next;}ListNode misEvent?midNode:midNode.next;while(m!null){ListNode tmpstack.pop();if(m.val!tmp.val){return false;}mm.next;}return true;}
}方法二链自反转对比法
解题思路找到中间节点后用栈辅助反转对比 解题方法 找到链表的中间节点并判断奇数还是偶数 继续利用双指针反转中间节点前的链表。 偶数从中间节点开始和反转链进行比较 奇数从中间节点后面的节点开始和反转链进行比较 若比较到最后一个节点都相等该链表为回文链表栈空或比较到最后一个节点 时间复杂度O(n) 空间复杂度O(1) public static boolean isPalindrome(ListNode head) {/*** [1,0,1]* head - 1 - 2 - 2 - 1 - null* head - 1 - 2 - 1 - null找到链表的中间节点并判断奇数还是偶数继续利用头插法反转中间节点前的链表。偶数从中间节点开始和反转链进行比较奇数从中间节点后面的节点开始和反转链进行比较若比较到最后一个节点都相等该链表为回文链表栈空或比较到最后一个节点*/if(head null){return false;}ListNode dummy new ListNode(-1);dummy.nexthead;ListNode slowdummy;ListNode fastdummy;ListNode midNodenull;Boolean isEventtrue;while (fast.next!null){slowslow.next;if(fast.next.next!null) {fast fast.next.next;} else{fastfast.next;isEventfalse;}}midNode isEvent ? slow.next : slow;ListNode p head;headnull;while (p!midNode){ListNode tmpp.next;p.nexthead;headp;ptmp;}//偶数从中间节点开始和反转链进行比较ListNode m isEvent ? midNode : midNode.next;boolean isPalindrometrue;phead;while (isPalindrome p!null){if(p.val!m.val){isPalindromefalse;}pp.next;mm.next;}// 还原链表p head;headmidNode;while (p!null){ListNode tmpp.next;p.nexthead;headp;ptmp;}return isPalindrome;}
