Solution For Palindrome Linked List

The Palindrome Linked List problem on LeetCode asks us to determine if a given singly-linked list is a palindrome. A palindrome is defined as a sequence of characters (or in this case, nodes) which reads the same backward as forward.

To solve this problem, we can use several approaches. One of the easiest methods is to reverse the second half of the linked list and then compare the first half with the reversed second half. Another method is to use a stack to store the first half of the linked list in reverse order and then compare it with the second half.

Here is a detailed solution using the first approach:

1. First, we need to determine the length of the linked list. We can do this by traversing the linked list and counting the number of nodes.

2. Next, we need to find the middle node of the linked list. We can use the fast and slow pointer method to find the middle node. The fast pointer moves two nodes at a time, while the slow pointer moves one node at a time. When the fast pointer reaches the end of the list, the slow pointer will be at the middle node.

3. We can then reverse the second half of the linked list. To do this, we need to split the linked list into two separate lists at the middle node. We can do this by setting the next pointer of the node before the middle node to null.

4. We can then reverse the second half of the linked list using the iterative method. We need to have three pointers: prev, current, and next. We set prev to null, current to the head of the second half, and next to the next node of current. We then iterate through the second half, setting the next pointer of the current node to prev, and moving each pointer one node at a time.

5. We can then compare the first half with the reversed second half. We can use two pointers, one starting from the head of the first half, and the other starting from the head of the reversed second half. We iterate through both halves, comparing each node one at a time. If at any point we find that two nodes are not equal, we can return false, since the linked list is not a palindrome. If we reach the end of both halves and all nodes are equal, we can return true, since the linked list is a palindrome.

Here is the Python code for the solution:

“`
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
if not head or not head.next:
return True

    # Find length of the linked list
    length = 0
    node = head
    while node:
        length += 1
        node = node.next

    # Find middle node
    middle = length // 2
    slow = head
    fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next

    # Reverse second half of the linked list
    prev = None
    current = slow.next
    while current:
        next = current.next
        current.next = prev
        prev = current
        current = next
    slow.next = prev

    # Compare first half with reversed second half
    node1 = head
    node2 = prev
    while node1 and node2:
        if node1.val != node2.val:
            return False
        node1 = node1.next
        node2 = node2.next

    return True

“`

The time complexity of this solution is O(n), where n is the length of the linked list, since we only need to traverse the linked list once. The space complexity is O(1), since we only need to use a constant amount of extra space to store pointers.

Step by Step Implementation For Palindrome Linked List

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        // base case
        if (head == null || head.next == null) {
            return true;
        }
        
        // find middle of the linked list
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        // reverse the second half of the linked list
        ListNode secondHead = slow.next;
        slow.next = null;
        ListNode prev = null;
        while (secondHead != null) {
            ListNode temp = secondHead.next;
            secondHead.next = prev;
            prev = secondHead;
            secondHead = temp;
        }
        
        // compare the first and second half
        while (prev != null) {
            if (head.val != prev.val) {
                return false;
            }
            head = head.next;
            prev = prev.next;
        }
        
        return true;
    }
}

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        # Base cases:
        # - empty list: considered a palindrome
        if head is None:
            return True
        # - single element list: considered a palindrome
        if head.next is None:
            return True
        
        # Find the end of the first half and reverse the second half.
        first_half_end = self.end_of_first_half(head)
        second_half_start = self.reverse_list(first_half_end.next)
        
        # Check whether or not there's a palindrome.
        result = True
        first_position = head
        second_position = second_half_start
        while result and second_position is not None:
            if first_position.val != second_position.val:
                result = False
            first_position = first_position.next
            second_position = second_position.next
        
        # Restore the list and return the result.
        first_half_end.next = self.reverse_list(second_half_start)
        return result

    def end_of_first_half(self, head):
        slow = head
        fast = head
        while fast.next is not None and fast.next.next is not None:
            slow = slow.next
            fast = fast.next.next
        return slow
    
    def reverse_list(self, head):
        previous = None
        current = head
        while current is not None:
            next_node = current.next
            current.next = previous
            previous = current
            current = next_node
        return previous

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function(head) {
    // edge case: if head is null or only has one node
    if (!head || !head.next) return true;
    
    // find the middle of the linked list
    let slow = head;
    let fast = head.next;
    
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    // reverse the second half of the linked list
    let prev = null;
    let curr = slow.next;
    
    while (curr) {
        let next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    
    // compare the first and second halves of the linked list
    slow.next = prev;
    let first = head;
    let second = slow.next;
    
    while (second) {
        if (first.val !== second.val) return false;
        first = first.next;
        second = second.next;
    }
    
    return true;
};

/**
 * 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) {
        // Base case
        if (head == nullptr || head->next == nullptr) {
            return true;
        }
        
        // Find the middle of the linked list
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        // Reverse the second half of the linked list
        ListNode* prev = nullptr;
        ListNode* curr = slow;
        while (curr != nullptr) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        
        // Compare the first and second half of the linked list
        while (prev != nullptr) {
            if (head->val != prev->val) {
                return false;
            }
            head = head->next;
            prev = prev->next;
        }
        
        return true;
    }
};

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public bool IsPalindrome(ListNode head) {
        // base case
        if (head == null || head.next == null) {
            return true;
        }
        
        // find middle node
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        // reverse second half
        ListNode secondHalfHead = ReverseList(slow.next);
        
        // compare first and second half
        ListNode firstHalfHead = head;
        while (firstHalfHead != null && secondHalfHead != null) {
            if (firstHalfHead.val != secondHalfHead.val) {
                return false;
            }
            firstHalfHead = firstHalfHead.next;
            secondHalfHead = secondHalfHead.next;
        }
        
        return true;
    }
    
    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;
    }
}