Question

Formatted question description: https://leetcode.ca/all/234.html

 234	Palindrome Linked List

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

 Example 1:

 Input: 1->2
 Output: false

 Example 2:

 Input: 1->2->2->1
 Output: true
 Follow up:
 Could you do it in O(n) time and O(1) space?

 @tag-linkedlist

Algorithm

The principle of using fast and slow pointers to find the midpoint,each time the fast pointer moves two steps and the slow pointer moves one step. When the fast pointer finishes, the position of the slow pointer is the midpoint.

After finding the midpoint, flip the linked list in the second half to compare in the order of palindrome.

Code

Java

  • 
    public class Palindrome_Linked_List {
    
        /**
         * Definition for singly-linked list.
         * public class ListNode {
         *     int val;
         *     ListNode next;
         *     ListNode(int x) { val = x; }
         * }
         */
        public boolean isPalindrome(ListNode head) {
    
            if (head == null) {
                return false;
            }
    
            // 2 pointers to find mid
            ListNode slowPrev = new ListNode(0);
            ListNode slow = head;
            ListNode fast = head;
    
            while (fast != null && fast.next != null) {
                fast = fast.next.next;
    
                slowPrev = slow;
                slow = slow.next;
            }
    
            // now slow aat middle
            slowPrev.next = null; // cut
    
            ListNode reversed2ndHalf = reverseNodeList(slow);
            ListNode p1 = head;
            ListNode p2 = reversed2ndHalf;
    
            while (p1 != null && p2 != null) {
                if (p1.val != p2.val) {
                    return false;
                }
    
                p1 = p1.next;
                p2 = p2.next;
            }
    
            return true;
        }
    
        private ListNode reverseNodeList(ListNode head) {
    
            ListNode dummy = new ListNode(0);
    
            ListNode current = head;
    
            while (current != null) {
                ListNode currenHead = dummy.next;
                ListNode nextHead = current.next;
    
                current.next = null; // cut current node out
    
                dummy.next = current;
                current.next = currenHead;
                current = nextHead;
            }
    
            return dummy.next;
        }
    }
    
  • // OJ: https://leetcode.com/problems/palindrome-linked-list/
    // Time: O(N)
    // Space: O(1)
    class Solution {
    private:
        int getLength(ListNode *head) {
            int len = 0;
            for (; head; head = head->next, ++len);
            return len;
        }
        ListNode *reverse(ListNode *head) {
            ListNode dummy(0);
            while (head) {
                ListNode *node = head;
                head = head->next;
                node->next = dummy.next;
                dummy.next = node;
            }
            return dummy.next;
        }
    public:
        bool isPalindrome(ListNode* head) {
            if (!head) return true;
            int len = (getLength(head) + 1) / 2;
            ListNode *p = head, *q;
            while (--len > 0) p = p->next;
            q = p->next;
            p->next = NULL;
            q = reverse(q);
            while (head && q) {
                if (head->val != q->val) return false;
                head = head->next;
                q = q->next;
            }
            return true;
        }
    };
    
  • # Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution(object):
      def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
    
        def reverseList(root):
          pre = None
          cur = root
          while cur:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
          return pre
    
        slow = fast = head
        while fast and fast.next:
          slow = slow.next
          fast = fast.next.next
    
        newHead = reverseList(slow)
        p1 = head
        p2 = newHead
        while p1 and p2:
          if p1.val != p2.val:
            return False
          p1 = p1.next
          p2 = p2.next
        return True
    
    

All Problems

All Solutions