Palindrome Linked List

                                            
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (!head || !head->next) {
            return true;
        }
        
        ListNode *slow = head, *fast = head;
        
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        slow->next = reverseList(slow->next);
        slow = slow->next;
        
        while (slow) {
            if (head->val != slow->val) {
                return false;
            }
            head = head->next;
            slow = slow->next;
        }
        
        return true;
    }
    
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        
        while (head) {
            ListNode* next = head->next;
            head->next = prev;
            prev = head;
            head = next;
        }
        
        return prev;
    }
};

                                            
/**
 * 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;
        }
        
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        slow.next = reverseList(slow.next);
        slow = slow.next;
        
        while (slow != null) {
            if (head.val != slow.val) {
                return false;
            }
            head = head.next;
            slow = slow.next;
        }
        
        return true;
    }
    
    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
}

                                            
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

bool isPalindrome(struct ListNode* head){
    if (head == NULL || head->next == NULL) {
        return true;
    }
    
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    
    while (fast->next != NULL && fast->next->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    struct ListNode* secondHalf = slow->next;
    slow->next = NULL;
    
    struct ListNode* prev = NULL;
    struct ListNode* curr = secondHalf;
    struct ListNode* next = NULL;
    
    while (curr != NULL) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    
    struct ListNode* p1 = head;
    struct ListNode* p2 = prev;
    
    while (p1 != NULL && p2 != NULL) {
        if (p1->val != p2->val) {
            return false;
        }
        p1 = p1->next;
        p2 = p2->next;
    }
    
    return true;
}

                                            
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public bool IsPalindrome(ListNode head) {
        if (head == null || head.next == null)
            return true;
        
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        slow.next = ReverseList(slow.next);
        slow = slow.next;
        
        while (slow != null) {
            if (head.val != slow.val)
                return false;
            head = head.next;
            slow = slow.next;
        }
        
        return true;
    }
    
    public ListNode ReverseList(ListNode head) {
        ListNode prev = null;
        
        while (head != null) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        
        return prev;
    }
}

                                            
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
var isPalindrome = function(head) {
    if (head === null) {
        return true;
    }

    let slow = head;
    let fast = head;

    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    let prev = null;
    let current = slow;

    while (current !== null) {
        const temp = current.next;
        current.next = prev;
        prev = current;
        current = temp;
    }

    let left = head;
    let right = prev;

    while (right !== null) {
        if (left.val !== right.val) {
            return false;
        }
        left = left.next;
        right = right.next;
    }

    return true;
};

                                            
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next? : ListNode) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function isPalindrome(head: ListNode | null): boolean {
    if (!head || !head.next) {
        return true;
    }

    let slow = head;
    let fast = head;

    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }

    let prev = null;
    let current = slow;

    while(current) {
        const next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }

    let left = head;
    let right = prev;

    while(right) {
        if (left.val !== right.val) {
            return false;
        }
        left = left.next;
        right = right.next;
    }

    return true;
};

                                            
class ListNode
    attr_accessor :val, :next
    def initialize(val = 0, _next = nil)
        @val = val
        @next = _next
    end
end

def is_palindrome(head)
    return true if head.nil?
    
    values = []
    current = head
    
    while !current.nil?
        values << current.val
        current = current.next
    end
    
    values == values.reverse
end

                                            
/**
 * Definition for singly-linked list.
 * class ListNode(_x: Int = 0, _next: ListNode = null) {
 *   var x: Int = _x
 *   var next: ListNode = _next
 * }
 */
object Solution {
    def isPalindrome(head: ListNode): Boolean = {
        def reverse(node: ListNode): ListNode = {
            var prev: ListNode = null
            var current = node
            while (current != null) {
                val nextTemp = current.next
                current.next = prev
                prev = current
                current = nextTemp
            }
            prev
        }
        
        def findMiddle(node: ListNode): ListNode = {
            var slow = node
            var fast = node
            while (fast != null && fast.next != null) {
                slow = slow.next
                fast = fast.next.next
            }
            slow
        }
        
        def compareLists(l1: ListNode, l2: ListNode): Boolean = {
            var p1 = l1
            var p2 = l2
            while (p1 != null && p2 != null) {
                if (p1.x != p2.x) return false
                p1 = p1.next
                p2 = p2.next
            }
            true
        }
        
        val mid = findMiddle(head)
        val reversed = reverse(mid)
        compareLists(head, reversed)
    }
}

                                            
// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
impl Solution {
    pub fn is_palindrome(head: Option<Box<ListNode>>) -> bool {
        let mut nums = vec![];
        let mut current = head;
        while let Some(node) = current {
            nums.push(node.val);
            current = node.next;
        }
        let mut i = 0;
        let mut j = nums.len() - 1;
        while i < j {
            if nums[i] != nums[j] {
                return false;
            }
            i += 1;
            j -= 1;
        }
        true
    }
}

To solve this coding challenge, we need to determine whether a given singly linked list is a palindrome. A linked list is considered a palindrome if it reads the same forwards and backwards. We aim to solve this within O(n) time complexity and O(1) space complexity, which means we have to be efficient both in terms of running time and auxiliary space usage.

Explanation

Initial Constraints Understanding :

We are given a singly linked list where the number of nodes can be up to 100,000.
Each node can contain an integer value between 0 and 9.

Key Concepts :

A palindrome reads the same forwards and backwards.
In O(n) time, we can traverse the list twice at most or use a two-pointer technique.
For O(1) space, we must be mindful not to use extra memory proportional to the input size.

Steps to Solve :

Step 1 : Use a slow and fast pointer technique to find the middle of the linked list.

The slow pointer moves one step at a time while the fast pointer moves two steps. When the fast pointer reaches the end, the slow pointer will be at the middle.

Step 2 : Reverse the second half of the linked list.

Starting from the middle, reverse the links of the second half of the list.

Step 3 : Compare both halves.

Traverse from the head to the middle and from the middle to the end (reversed second half) and compare each corresponding node.
If all corresponding nodes are equal, the list is a palindrome.

Step 4 : Restore the original list (optional).

Depending on requirements, you might want to restore the list to its original state by reversing back the second half.

Detailed Steps in Pseudocode

Step 1: Find the Middle of the Linked List

                                            
# Initialize two pointers, slow and fast.
pointer_slow = head
pointer_fast = head

# Move the slow pointer one step and the fast pointer two steps at a time.
# When the fast pointer reaches the end, the slow pointer will be at the middle.
while pointer_fast is not NULL and pointer_fast.next is not NULL:
    pointer_slow = pointer_slow.next
    pointer_fast = pointer_fast.next.next

Step 2: Reverse the Second Half of the Linked List

                                            
# Initialize previous pointer to NULL.
previous_node = NULL
current_node = pointer_slow

# Reverse the second half of the list.
while current_node is not NULL:
    temp_next = current_node.next  # Store next node.
    current_node.next = previous_node  # Reverse current node's pointer.
    previous_node = current_node  # Move to the next node.
    current_node = temp_next

Step 3: Compare Both Halves

                                            
# Initialize pointers to start of the list and start of the reversed second half.
pointer_left = head
pointer_right = previous_node

# Compare the values in the two halves.
while pointer_right is not NULL:
    if pointer_left.val != pointer_right.val:
        # If values do not match, it's not a palindrome.
        return False
    pointer_left = pointer_left.next
    pointer_right = pointer_right.next

# If all values matched, it is a palindrome.
return True

Step 4: Optional (Restore Original List)

                                            
# Reverse the second half back to its original form (if needed).
previous_node = NULL
current_node = pointer_right

while current_node is not NULL:
    temp_next = current_node.next
    current_node.next = previous_node
    previous_node = current_node
    current_node = temp_next

By following these detailed steps methodically, we can efficiently determine if the given linked list is a palindrome in linear time and constant space.