Given a singly linked list, determine if it is a palindrome.

Follow up:

Could you do it in O(n) time and O(1) space?

Could you do it in O(n) time and O(1) space?

**Understand the problem:**

Since the problem asks for O(n) time and O(1) space, we cannot create additional data structure to store the values. The steps to solve the problem are:

-- 1. Find the middle of the list.

-- 2. Reverse the right half of the list.

-- 3. Compare the left half and right half.

**Code (Java):**

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public boolean isPalindrome(ListNode head) { if (head == null || head.next == null) { return true; } int len = getLength(head); ListNode mid = findMiddle(head); ListNode newHead; if (len % 2 == 0) { newHead = mid.next; mid.next = null; } else { ListNode dummyNode = new ListNode(mid.val); dummyNode.next = mid.next; newHead = dummyNode; } // Step 2: reverse the list newHead = reverseList(newHead); // Step 3: compare the list ListNode p = head; ListNode q = newHead; while (p != null && q != null) { if (p.val != q.val) { return false; } p = p.next; q = q.next; } return true; } private int getLength(ListNode head) { ListNode p = head; int len = 0; while (p != null) { len++; p = p.next; } return len; } private ListNode findMiddle(ListNode head) { ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; } return slow; } private ListNode reverseList(ListNode head) { ListNode prev = null; ListNode curr = head; while (curr != null) { ListNode next = curr.next; curr.next = prev; prev = curr; curr = next; } return prev; } }

Isnt this changing the given input.

ReplyDeleteWe can do it using stack..

1. find length

2. traverse to mid using p1

3. from mid to end put elements on stack (if length is odd dont put mid on stack go next)

4. using another pointer p2 - traverse from head to mid -- popping from stack and checking