Palindrome Linked List

Determining if a singly linked list is a palindrome involves checking whether the elements in the first half of the list are the same as those in the second half but in reverse order.

Here’s a simple approach to check if a linked list is a palindrome:

1. Find the Middle of the List: You can do this using the slow and fast pointer technique, where the slow pointer advances one step, and the fast pointer advances two steps. When the fast pointer reaches the end of the list, the slow pointer will be at the middle.

2. Reverse the Second Half: From the middle of the list, reverse the second half of the linked list.

3. Compare the First and Second Halves: Compare the elements of the first half of the list with the reversed second half. If they are the same, the linked list is a palindrome.

4. Restore the Original List Structure (Optional): If you want to keep the original structure of the list, you should reverse the second half again.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        slow = fast = head

        # Find the middle
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # Reverse the second half
        prev = None
        while slow:
            next_node = slow.next
            slow.next = prev
            prev = slow
            slow = next_node

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

        return True

This code first finds the middle of the linked list, reverses the second half, and then compares both halves to check if the linked list is a palindrome. It returns True if the linked list is a palindrome, False otherwise.

Define the Terms

palindrome : Reads the same forward and backwards Instead of string, we have numbers 1-2 1-2-2-1

Define the Interface Input: Head of the linked list Output: boolean (palindrome or not)

Analyze the Input and Output

Identify the Invariants

Identify the constraints

• T: O(N)
• S: O(1)

Search the Problem Space

Classify the Problem

Analyze the Examples

Solve the Problem by Hand

Describe the Pattern

Distill the Observations to Create Insights

Brute Force Approach Recursive approach becomes messy in this case. Going backward is problematic (not doubly linked list)

Wishful Thinking and Working Backwards Tower of Hanoi

Imagine you can somehow position the pointers at the appropriate nodes to do the comparison. What kind of preprocessing can I do to make that happen? We can only move forward.

What is the size of the linked list, so that I can split them into two. - Even number of elements (1-2, 2-1) - Odd number of elements (1-2-3, 2-1) Where should the middle element be added to the first list or second list? We don’t really care. We still stop comparing when we not longer have nodes in the smaller list.

First half and second half can be split. Reverse the second half

1->2 -> 2->1 1->2 -> 1->2

1->2 -> 2->1 1->2 -> 1->2

Analyze Time and Space Complexity

Time: O( ) Space: O( )

Outline the Solution

1. We will split the given linked list by half

2. Reverse the second half

3. Compare and check if it is palindrome

4. Revert the linked list to its orignal list

5. Find the end of the first half

6. Reverse the linked list

7. Palindrome

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

def end_of_first_half(head)
   fast = head
    slow = head

    while (fast.next && fast.next.next)
       fast = fast.next.next
        slow = slow.next
    end
    slow
end

  1->2->3
  2->nil
3 ->  2 -> 1

previous | current       | next_node  | current.next
nil          head (1)         2             2
1            2
2             3                3  
                                nil
3              nil


```ruby
def reverse_list(head)
   previous = nil
   current = head

    while current
       next_node = current.next
       current.next, previous = previous, current
       current = next_node
    end

    return previous
end

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

# Definition for singly-linked list.
# class ListNode
#     attr_accessor :val, :next
#     def initialize(val = 0, _next = nil)
#         @val = val
#         @next = _next
#     end
# end
# @param {ListNode} head
# @return {Boolean}
def is_palindrome(head)
    if head.nil?
        return true
    end

    first_half_end = end_of_first_half(head)
    second_half_start = reverse_list(first_half_end.next)
    left = head
    right = second_half_start

    result = true
    while right && left
        if left.val != right.val
            result = false
        end

        left = left.next
        right = right.next
    end

    first_half_end.next = reverse_list(second_half_start)

    return result
end

Palindrome Linked List excerpt: This covers the basic building blocks such as fast and slow pointers to find the middle of the linked list and reversing the linked list. tags: fast-and-slow-pointers find-middle-of-linked-list reverse-linked-list

Given the head of a singly linked list, return true if it is a palindrome.

Constraints

• The number of nodes in the list is in the range [1, 105].
• 0 <= Node.val <= 9

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

Thought Process

Define the Term

palindrome : Reads the same forward and backwards. Instead of string, we have numbers.

1-2 1-2-2-1

Define the Interface

Input: Head of the linked list Output: boolean (palindrome or not)

Identify the constraints

• T: O(N)
• S: O(1)

Recursive approach becomes messy in this case. Going backward is problematic (not doubly linked list).

Wishful Thinking and Working Backwards

Tower of Hanoi is a good example for working backwards. Let’s apply it to this problem. Imagine you can somehow position the pointers at the appropriate nodes to do the comparison. What kind of preprocessing can I do to make that happen? We can only move forward. What is the size of the linked list, so that I can split them into two?

• Even number of elements (1-2, 2-1)
• Odd number of elements (1-2-3, 2-1)

Where should the middle element be added to the first list or second list? We don’t really care. We still stop comparing when we no longer have nodes in the smaller list.

• First half and second half can be split.
• Reverse the second half

1->2 -> 2->1 1->2 -> 1->2

1->2 -> 2->1 1->2 -> 1->2

Solution Outline

1. We will split the given linked list by half
2. Reverse the second half
3. Compare and check if it is palindrome
4. Revert the linked list to its original list

Tasks

1. Find the end of the first half

2. Reverse the linked list

3. Palindrome check

4. Steps to solve the problem:

• Create a new linked list.
• Reverse the linked list.
• Traverse at the same time on both lists to check for palindrome.

Modification:

• Use fast and slow pointer
• Get the middle of the linked list. For the first half, reverse the elements.
• Get the other half and compare

2. Use a stack - Iterative Approach

• Traverse the linked list and get the total length
• Divide that by 2
• Traverse the linked list again, for length = half
• Check the top of the stack, if there is a mismatch, return false otherwise return true

3. Recursive Approach

• Traversal

  • Get to the base case, single node.
  • Pass through inside a recursive function, a pointer. Initially the head.

• What is the repeated unit of work?

  • Checking if the node.val == pointer.val, if they are not the same => return false

• Where do you initialize before recursion?

  • Helper can be used to initialize the first and last pointers

• Recursive case

  • If we have a helper, what are the parameters to the recursive call?

  • two parameters (pointers)

  • Comparison of two elements - Compare the first and last element. Return false if they are different

  • What do we do after the recursive call?

    • We have reached the end of the linked list
    • We can start comparing last node with the first node
    • Before returning - Set the pointer to the next, currently at 2

4. Traverse first half, by the time we reach middle

Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

def end_of_first_half(head)
  fast = head
  slow = head
  
  # fast must stop at the last node
  while (fast.next && fast.next.next)
    fast = fast.next.next
    slow = slow.next
  end
  
  # slow will be at the middle node
  return slow
end

def reverse_list(head)
  previous = nil
  current = head
    
  while current
    next_node = current.next
    current.next, previous = previous, current
    current = next_node
  end
  
  return previous
end

# Definition for singly-linked list.
# class ListNode
#     attr_accessor :val, :next
#     def initialize(val = 0, _next = nil)
#         @val = val
#         @next = _next
#     end
# end
# @param {ListNode} head
# @return {Boolean}
def is_palindrome(head)
  if head.nil?
    return true
  end
    
  first_half_end = end_of_first_half(head)
  second_half_start = reverse_list(first_half_end.next)
  left = head
  right = second_half_start
    
  result = true
    
  while (result && right)
    if left.val != right.val 
      result = false
    end
    
    left = left.next
    right = right.next
  end
    
  first_half_end.next = reverse_list(second_half_start)
    
  return result
end

Building Blocks

• Fast and Slow Pointers to Find Middle of Linked List
• Reverse Linked List

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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

        slow = fast = head
        reversed_list = None

        while fast is not None and fast.next is not None:
            tmp = slow

            slow = slow.next
            fast = fast.next.next

            tmp.next = reversed_list
            reversed_list = tmp

        if fast is not None:
            slow = slow.next

        while reversed_list is not None and reversed_list.val == slow.val:
            reversed_list = reversed_list.next
            slow = slow.next

        return reversed_list is None

Problem Classification

1. Data Structures: The problem involves working with Linked Lists, a fundamental data structure.

2. Algorithms: The problem requires the use of specific algorithms or techniques, namely: Two-pointer technique and List reversal.

3. Problem Type: This is a Palindrome problem, which is a common type of problem in the realm of String and List manipulation.

4. Complexity Analysis: Given the two-pointer and reversal techniques used, understanding of Time and Space complexity analysis would be essential for evaluating the efficiency of the solution.

This is a Linked List manipulation problem, requiring knowledge of certain algorithms, where the task is to determine whether the given list is a Palindrome or not.

Language Agnostic Coding Drills

1. Understanding Linked Lists: The first fundamental concept that one must understand for this problem is how linked lists work. This includes understanding the structure of a node, what head and next refer to, and the concept of singly linked lists.

2. Traversal in a Linked List: The second key learning point is how to traverse through a linked list. This involves iterating over the list by continuously moving to the ’next’ node until you reach the end of the list (i.e., the next node is None).

3. Two-pointer Technique: This problem makes use of the slow-fast (or hare and tortoise) pointer technique, where two pointers traverse the list at different speeds. This is a common technique for detecting cycles in a list or finding the middle element, as is the case in this problem.

4. Reversing a Linked List: This is a critical concept required for this problem. This involves changing the ’next’ pointers of every node so that they point to the previous node instead of the next node.

5. Comparing Linked Lists: The final step of the problem involves comparing the reversed first half of the list to the second half of the list. This is another essential skill when working with linked lists.

Step by Step Approach:

1. Initialization: Start with initializing two pointers, slow and fast, at the head of the linked list.

2. Find the Middle: Traverse the linked list to find the middle node. Move slow one step at a time and fast two steps at a time. When fast reaches the end, slow will be at the middle.

3. Reverse the First Half: While finding the middle, reverse the first half of the linked list. Store the reversed part in a separate variable (reversed_list).

4. Adjustment for Odd Number of Nodes: If the total number of nodes is odd, move the slow pointer one step further.

5. Compare the Two Halves: Now, the problem reduces to comparing two halves of a linked list. One is the reversed_list and the other starts from slow.

6. Final Output: If all corresponding nodes in both halves are equal, return True, else return False. If we exhaust the reversed_list and every value was the same for both lists, we have a palindrome.

Targeted Drills in Python

Here are the coding drills for the problem. We will implement each fundamental concept one by one and gradually build up to the final solution:

1. Understanding Linked Lists: Before you start, you should know how to create a linked list. Here is how you can define a Node for a singly linked list in Python.

1
2
3
4

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

2. Traversal in a Linked List: The next concept you should understand is how to traverse a linked list. Here is a simple code that does that:

1
2
3
4
5

def traverse_linked_list(head):
    curr_node = head
    while curr_node is not None:
        print(curr_node.val)
        curr_node = curr_node.next

3. Two-pointer Technique: You should be comfortable using two pointers to traverse a linked list. Here is a simple code that uses this technique to find the middle of a linked list:

1
2
3
4
5
6
7

def find_middle(head):
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    return slow

4. Reversing a Linked List: This is a critical step for this problem. Here is how you can reverse a linked list:

1
2
3
4
5
6
7
8
9

def reverse_linked_list(head):
    prev_node = None
    curr_node = head
    while curr_node is not None:
        next_node = curr_node.next
        curr_node.next = prev_node
        prev_node = curr_node
        curr_node = next_node
    return prev_node

5. Comparing Linked Lists: The final drill is to compare two linked lists. This will be used to check if the first half and the second half of the list are the same:

1
2
3
4
5
6
7

def compare_lists(l1, l2):
    while l1 is not None and l2 is not None:
        if l1.val != l2.val:
            return False
        l1 = l1.next
        l2 = l2.next
    return True

Finally, you can combine all these drills to solve the problem:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

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

        # Find middle
        slow = head
        fast = head
        prev = None

        while fast is not None and fast.next is not None:
            fast = fast.next.next
            next_node = slow.next
            slow.next = prev
            prev = slow
            slow = next_node

        # If the list has an odd number of elements, skip the middle element
        if fast is not None:
            slow = slow.next

        return self.compare_lists(prev, slow)

    def compare_lists(self, l1, l2):
        while l1 is not None and l2 is not None:
            if l1.val != l2.val:
                return False
            l1 = l1.next
            l2 = l2.next
        return True