234. Palindrome Linked List |
您所在的位置：网站首页 › linkedlist的peek › 234. Palindrome Linked List |
|
Question
Given the head of a singly linked list, return true if it is a palindrome. Solution 1快慢指针，快指针遍历到底时慢指针正好到一半。根据快指针的位置判断奇数个还是偶数个。如果是奇数个则翻转链表时需要向前移动一位。 接下来翻转后半段链表。翻转完成后从第一段的头部和翻转过的链表头部开始遍历。如果两个节点的值不同则返回false。 遍历完毕返回true。 Code1234567891011121314151617181920212223242526272829303132333435363738/** * 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) { int len = 0; ListNode slow = head, fast = head; while(fast != null && fast.next != null){ slow = slow.next; fast = fast.next.next; } ListNode curr = fast == null ? slow : slow.next, prev = null; //make sure curr is the head of the 2nd part while(curr != null){ //reverse the 2nd part of the nodes ListNode temp = curr.next; //preserve nodes that after current node curr.next = prev; //add previous node to the current node's next prev = curr; //save previous node curr = temp; //update current node } while(head != null && prev != null){ if(head.val != prev.val) return false; prev = prev.next; head = head.next; } return true; }} Solution 2快慢指针的原理，不是记录长度而是当快指针遍历到链表尾时停止。然后对照栈内的值是否和剩余的值相等。 Code123456789101112131415161718192021222324252627282930313233/** * 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 slow = head, fast = head; Stack stack = new Stack(); while(fast != null && fast.next != null){ stack.add(slow); slow = slow.next; fast = fast.next.next; } if(fast != null) slow = slow.next; while(!stack.isEmpty()){ if(stack.pop().val != slow.val) return false; slow = slow.next; } return true; }} Solution 3回文，先计算链表长度。记录链表长度是否为奇数。 如果链表长度为偶数，则将一半的节点放入栈中。如果为奇数则抛弃一个节点。剩下一半的节点和栈顶节点比较，如果值不相同则返回false。 遍历完成返回true。 Code1234567891011121314151617181920212223242526272829303132333435363738/** * 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) { int len = 0; ListNode root = head; Stack stack = new Stack(); while(root != null){ root = root.next; len++; } root = head; for(int i = 0; i < len/2; i++){ stack.add(root); root = root.next; } if(len % 2 != 0) root = root.next; for(int i = 0; i < len/2; i++){ if(stack.peek().val == root.val) stack.pop(); else return false; root = root.next; } return true; }} |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |