题目
请判断一个链表是否为回文链表。
示例1:
示例2:
进阶:
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?
思路
用 栈+快慢指针 或者 快慢指针+反转链表
快慢指针是用来寻找中间节点。栈是用来反转链表。
代码
- 栈 + 快慢指针
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
|
class Solution { public boolean isPalindrome(ListNode head) { if(head==null||head.next==null) return true; Stack<ListNode> stack = new Stack<>(); ListNode fast = head; ListNode low = head; while(fast!=null&&fast.next!=null){ fast = fast.next.next; stack.push(low); low = low.next; if(fast!=null&&fast.next==null) low = low.next; } while(!stack.empty()){ if(stack.pop().val!=low.val) return false; low = low.next; } return true; } }
|
- 快慢指针 + 反转链表
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43
|
class Solution { public boolean isPalindrome(ListNode head) { if(head==null||head.next==null) return true; ListNode fast = head; ListNode low = head; while(fast!=null&&fast.next!=null){ fast = fast.next.next; low = low.next; if(fast!=null&&fast.next==null) low = low.next; } ListNode compNode = reverseLinkedList(low); while(compNode!=null){ if(compNode.val!=head.val) return false; compNode = compNode.next; head = head.next; } return true; } public ListNode reverseLinkedList(ListNode head){ ListNode preNode = null; ListNode curNode = head; while(curNode!=null){ ListNode temp = curNode.next; curNode.next = preNode; preNode = curNode; curNode = temp; } return preNode; } }
|
题目链接