首页 > 代码库 > CTCI 2.7
CTCI 2.7
Implement a function to check if a linked list is a palindrome.
Reverse the second half of the list and then compare it with the first half.
/* Assume that we can destroy the list, reverse the second half of the list and compare it with the firsthalf. If we were not permit to destroy the list, change the list to an array and then check if it is a palidrome.*/public class IsPalidrome { public boolean isPalidrome(Node head) { if(head == null || head.next == null) return true; int cnt = 0; Node temp = head; while(temp != null) { cnt++; temp = temp.next; } int half = cnt / 2; temp = head; while(half > 1) { temp = temp.next; half--; } Node sent = new Node(0); //break the list into two parts Node temp1 = temp.next, temp2 = temp.next; temp.next = null; //reverse the second half while(temp1 != null) { temp2 = temp1.next; temp1.next = sent.next; sent.next = temp1; temp1 = temp2; } //check if it is palidrome Node head1 = head, head2 = sent.next; while(head1 != null && head2 != null) { if(head1.val == head2.val) { head1 = head1.next; head2 = head2.next; } else return false; } return true; } public static void main(String[] args) { Node node1 = new Node(1); Node node11 = new Node(1); node1.next = node11; Node node2 = new Node(1); Node node22 = new Node(2); node2.next = node22; Node node31 = new Node(1); Node node32 = new Node(2); Node node33 = new Node(1); node31.next = node32; node32.next = node33; Node node41 = new Node(1); Node node42 = new Node(3); Node node43 = new Node(2); Node node44 = new Node(1); node41.next = node42; node42.next = node43; node43.next = node44; IsPalidrome ip = new IsPalidrome(); System.out.println(ip.isPalidrome(node1)); System.out.println(ip.isPalidrome(node2)); System.out.println(ip.isPalidrome(node31)); System.out.println(ip.isPalidrome(node41)); }}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。