Function to check if a singly linked list is palindrome | GeeksforGeeks

Also check LeetCode – Palindrome Linked List

Function to check if a singly linked list is palindrome | GeeksforGeeks
Given a singly linked list of characters, write a function that returns true if the given list is palindrome, else false.

METHOD 2 (By reversing the list)This method takes O(n) time and O(1) extra space.
1) Get the middle of the linked list.
2) Reverse the second half of the linked list.
3) Check if the first half and second half are identical.
4) Construct the original linked list by reversing the second half again and attaching it back to the first half

bool isPalindrome(struct node *head)

{

    struct node *slow_ptr = head, *fast_ptr = head;

    struct node *second_half, *prev_of_slow_ptr = head;

    struct node *midnode = NULL;  // To handle odd size list

    bool res = true; // initialize result

    if (head!=NULL)

    {

        /* Get the middle of the list. Move slow_ptr by 1

          and fast_ptrr by 2, slow_ptr will have the middle

          node */

        while (fast_ptr != NULL && fast_ptr->next != NULL)

        {

            fast_ptr = fast_ptr->next->next;

            /*We need previous of the slow_ptr for

             linked lists  with odd elements */

            prev_of_slow_ptr = slow_ptr;

            slow_ptr = slow_ptr->next;

        }

        /* fast_ptr would become NULL when there are even elements in list.

           And not NULL for odd elements. We need to skip the middle node

           for odd case and store it somewhere so that we can restore the

           original list*/

        if (fast_ptr != NULL)

        {

            midnode = slow_ptr;

            slow_ptr = slow_ptr->next;

        }

        // Now reverse the second half and compare it with first half

        second_half = slow_ptr;

        prev_of_slow_ptr->next = NULL; // NULL terminate first half

        reverse(&second_half);  // Reverse the second half

        res = compareLists(head, second_half); // compare

        /* Construct the original list back */

         reverse(&second_half); // Reverse the second half again

         if (midnode != NULL)  // If there was a mid node (odd size case) which                         

                               // was not part of either first half or second half.

         {

            prev_of_slow_ptr->next = midnode;

            midnode->next = second_half;

         }

         else  prev_of_slow_ptr->next = second_half;

    }

    return res;

}

X. http://www.programcreek.com/2014/07/leetcode-palindrome-linked-list-java/
We can create a new list in reversed order and then compare each node. The time and space are O(n).

public boolean isPalindrome(ListNode head) {
    if(head == null)
        return true;
 
    ListNode p = head;
    ListNode prev = new ListNode(head.val);
 
    while(p.next != null){
        ListNode temp = new ListNode(p.next.val);
        temp.next = prev;
        prev = temp;
        p = p.next;
    }
 
    ListNode p1 = head;
    ListNode p2 = prev;
 
    while(p1!=null){
        if(p1.val != p2.val)
            return false;
 
        p1 = p1.next;
        p2 = p2.next;
    }
 
    return true;
}

Solution 2 
We can use a fast and slow pointer to get the center of the list, then reverse the second list and compare two sublists. The time is O(n) and space is O(1).

public boolean isPalindrome(ListNode head) {
 
    if(head == null || head.next==null)
        return true;
 
    //find list center
    ListNode fast = head;
    ListNode slow = head;
 
    while(fast.next!=null && fast.next.next!=null){
        fast = fast.next.next;
        slow = slow.next;
    }
 
    ListNode secondHead = slow.next;
    slow.next = null;
 
    //reverse second part of the list
    ListNode p1 = secondHead;
    ListNode p2 = p1.next;
 
    while(p1!=null && p2!=null){
        ListNode temp = p2.next;
        p2.next = p1;
        p1 = p2;
        p2 = temp;
    }
 
    secondHead.next = null;
 
    //compare two sublists now
    ListNode p = (p2==null?p1:p2);
    ListNode q = head;
    while(p!=null){
        if(p.val != q.val)
            return false;
 
        p = p.next;
        q = q.next;
 
    }
 
    return true;
}

http://bookshadow.com/weblog/2015/07/10/leetcode-palindrome-linked-list/
1). 使用快慢指针寻找链表中点
2). 将链表的后半部分就地逆置，然后比对前后两半的元素是否一致
3). 恢复原始链表的结构（可选） def isPalindrome(self, head): if head is None: return True #find mid node fast = slow = head while fast.next and fast.next.next: slow = slow.next fast = fast.next.next #reverse second half p, last = slow.next, None while p: next = p.next p.next = last last, p = p, next #check palindrome p1, p2 = last, head while p1 and p1.val == p2.val: p1, p2 = p1.next, p2.next #resume linked list(optional) p, last = last, None while p: next = p.next p.next = last last, p = p, next slow.next = last return p1 is None
http://www.codebytes.in/2014/12/checking-if-singly-linked-list-is.html
Method #2
Use a stack as described in the algorithm.

Algorithm:
1. Find the length of the linked list.
2. Put first half of the linked list in a stack.
3. Now from the beginning of the second half, check if the content popped from the stack is the same as the current node in the second half advancing to the end.
4. Take care to see if the length of the list is odd, the beginning of the second list is from size/2+1th index.

METHOD 1 (Use a Stack) ==> codebytes solution is better

A simple solution is to use a stack of list nodes. This mainly involves three steps.
1) Traverse the given list from head to tail and push every visited node to stack.
2) Traverse the list again. For every visited node, pop a node from stack and compare data of popped node with currently visited node.
3) If all nodes matched, then return true, else false.

Time complexity of above method is O(n), but it requires O(n) extra space. Following methods solve this with constant extra space.

    bool isPalindrome(ListNode* head) {
        if (!head || !head->next) return true;
        ListNode *slow = head, *fast = head;
        stack<int> s;
        s.push(head->val);
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
            s.push(slow->val);
        }
        if (!fast->next) s.pop();
        while (slow->next) {
            slow = slow->next;
            int tmp = s.top(); s.pop();
            if (tmp != slow->val) return false;
        }
        return true;
    }

METHOD 3 (Using Recursion)
Use two pointers left and right. Move right and left using recursion and check for following in each recursive call.
1) Sub-list is palindrome.
2) Value at current left and right are matching.

If both above conditions are true then return true.

The idea is to use function call stack as container. Recursively traverse till the end of list. When we return from last NULL, we will be at last node. The last node to be compared with first node of list.

In order to access first node of list, we need list head to be available in the last call of recursion. Hence we pass head also to the recursive function. If they both match we need to compare (2, n-2) nodes. Again when recursion falls back to (n-2)nd node, we need reference to 2nd node from head. We advance the head pointer in previous call, to refer to next node in the list.

However, the trick in identifying double pointer. Passing single pointer is as good as pass-by-value, and we will pass the same pointer again and again. We need to pass the address of head pointer for reflecting the changes in parent recursive calls.

// Initial parameters to this function are &head and head

bool isPalindromeUtil(struct node **left, struct  node *right)

{

   /* stop recursion when right becomes NULL */

   if (right == NULL)

      return true;

   /* If sub-list is not palindrome then no need to

       check for current left and right, return false */

   bool isp = isPalindromeUtil(left, right->next);

   if (isp == false)

      return false;

   /* Check values at current left and right */

   bool isp1 = (right->data == (*left)->data);

   /* Move left to next node */

   *left = (*left)->next;

   return isp1;

}

// A wrapper over isPalindromeUtil()

bool isPalindrome(struct node *head)

{

   isPalindromeUtil(&head, head);

}

http://algorithm.yuanbin.me/zh-cn/linked_list/check_if_a_singly_linked_list_is_palindrome.html
递归需要两个重要条件，递归步的建立和递归终止条件。对于回文比较，理所当然应该递归比较第 i 个节点和第 n-i 个节点，那么问题来了，如何构建这个递归步？大致可以猜想出来递归的传入参数应该包含两个节点，用以指代第 i 个节点和第 n-i 个节点。返回参数应该包含布尔值(用以提前返回不是回文的情况)和左半部分节点的下一个节点(用以和右半部分的节点进行比较)。由于需要返回两个值，在 Java 中需要使用自定义类进行封装，C/C++ 中则可以使用指针改变在递归调用后进行比较时节点的值。

public class Solution {
    private class Result {
        ListNode node;
        boolean isp;
        Result(ListNode aNode, boolean ret) {
               isp = ret;
               node = aNode;
               }
    }

    public Result helper(ListNode left, ListNode right) {
        Result result = new Result(left, true);

        if (right == null) return result;

        result = helper(left, right.next);
        boolean isp = (right.val == result.node.val);
        if (!isp) {
            result.isp = false;
        }
        result.node = result.node.next;

        return result;
    }

    public boolean isPalindrome(ListNode head) {
        Result ret = helper(head, head);
        return ret.isp;
    }

http://www.codebytes.in/2014/12/checking-if-singly-linked-list-is.html

class Pair{
        LinkedList.Node node;
        boolean equal;
        
        Pair(LinkedList.Node node, boolean equal){
            this.node = node;
            this.equal = equal;
        }
}

public class Code{ 
    
    //Recursive solution
    static Pair check(LinkedList.Node node, int length){ 
        if(length == 1) return new Pair(node.next, true);
        else if(length==0)return new Pair(node, true);
        Pair r = check(node.next, length-2);
        if(r.node == null)return r;
        if(r.equal){
            System.out.println("*Recursive*: Comparing "+r.node+" with "+node);
            if(r.node.equals(node))return new Pair(r.node.next, true);
            else return new Pair(null, false);
        }
        return new Pair(null, false);
    }

https://github.com/ajitkoti/Algorithms/blob/master/src/com/interview/algorithms/linkedlist/CheckIfALinkedListIsPalindrome.java

	private static boolean isPalindrome(Node head) { return isPalindromeUtil(head, head);
	}
	// Initial parameters to this function are &head and head
	private static boolean isPalindromeUtil(Node left, Node right) {
	/* stop recursion when right becomes NULL */
	if (right == null)
	return true;
	/*
	* If sub-list is not palindrome then no need to check for current left
	* and right, return false
	*/
	boolean isp = isPalindromeUtil(left, right.getNextNode());
	if (isp == false)
	return false;
	/* Check values at current left and right */
	boolean isp1 = (right.getData() == left.getData());
	/* Move left to next node */
	left = left.getNextNode();
	return isp1;
	}

Read full article from Function to check if a singly linked list is palindrome | GeeksforGeeks