题目:给定一个链表的头节点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 删除。