判断一个链表是否为回文结构
原创
题目：给定一个链表的头节点head， 请判断该链表是否为回文结构。 例如： 1->2->1， 返回true。 1->2->2->1， 返回true。
15->6->15， 返回true。 1->2->3， 返回false。
进阶： 如果链表长度为N， 时间复杂度达到O(N)， 额外空间复杂度达到O(1)
解法一：
将整个的链表的数据入栈
public static boolean isPalindrome1(ListNode head) {
if (head == null || head.next == null) return true;
Stack<Integer> stack = new Stack<>();
ListNode dunny = new ListNode(0);
dunny.next = head;
while (dunny.next != null){
stack.push(dunny.next.val);
dunny = dunny.next;
}
while (!stack.isEmpty()){
if (stack.pop()!= head.val) return false;
head = head.next;
}
return true;
}解法二：
将后半部分入栈
public static boolean isPalindrome2(ListNode head) {
if (head == null || head.next == null) return true;
ListNode dunny = new ListNode(0);
ListNode fast = dunny;
ListNode slow = dunny;
dunny.next = head;
while (fast!=null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
fast = slow .next;
Stack<Integer> stack = new Stack<>();
while (fast != null){
stack.add(fast.val);
fast = fast.next;
}
while (!stack.isEmpty()){
if (stack.pop() != head.val) return false;
head = head.next;
}
return true;
}解法三：
将后半部分逆序后比较然后再回复原来的链表
public static boolean isPalindrome3(ListNode head) {
if (head == null || head.next == null) return true;
ListNode dunny = new ListNode(0);
ListNode fast = dunny;
ListNode slow = dunny;
dunny.next = head;
while (fast!=null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
fast = slow.next;
slow.next = null;
ListNode temp = null;
while (fast!= null){
temp = fast.next;
fast.next = slow;
slow = fast;
fast = temp;
}
temp = slow;
fast = head;
boolean res = true;
while (fast != null && slow != null){
if (fast.val != slow.val){
res = false;
break;
}
fast = fast.next;
slow = slow.next;
}
slow = temp.next;
temp.next = null;
while (slow != null){
fast = slow.next;
slow.next = temp;
temp = slow;
slow = fast;
}
return res;
}原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录