Palindrome: String and Linked List

4 min readOct 30, 2022

Palindrome check in string using two pointers technique. Two pointers are set initially at the start and end of the string, and then move toward each other if the two characters referenced by the pointers are matched. In linked list, find the middle of the linked list and then reverse the the linked list from middle to end. Check if node’s value in the first half (head to mid-1) and second half (mid to end) of the linked list are matched one by one.

Table of Contents· Palindrome
· Palindrome String
  ∘ Approach
  ∘ Graphical Explanation
  ∘ Code Implementation
    ∘ Complexity
    ∘ Golang
    ∘ Python
· Palindrome Linked List
  ∘ Approach
  ∘ Graphical Explanation
  ∘ Code Implementation
    ∘ Complexity
    ∘ Golang
    ∘ Python

Palindrome

A sequence is the same both forwards and backwards. A single character is considered to be a palindrome

Palindrome String

Approach

Use two pointers technique. Set up two pointers, left and right, at each end. Then check whether if two characters pointed by left and right are matched or not. If they are mismatch, the string is not a palindrome. Otherwise, move toward each other and compare until left and right pointers cross each other.

Graphical Explanation

step1: set up left and right pointers at each end
step2: match two characters referenced by left and right pointers

string[left] != string[right] → not a palindrome
string[left] == string[right] → left += 1, right -= 1

Repeat step2 until left and right pointers cross each other.

Code Implementation

Complexity

Time: O(n)
Sapce: O(1)
n: the length of the string

Golang

Python

Palindrome Linked List

Approach

Find the middle of the linked list. If the linked list has an even number of nodes, find the second middle node. Then reverse the linked list from middle to end. Finally, check if node’s value in the first half (head to mid-1) and second half (mid to end) of the linked list are matched one by one.

Find the middle of the linked list
Use slow and fast pointers begin at the head of the linked list. Slow pointer moves one step and fast pointer move two steps at a time. When fast pointer reaches the end(fast is null or fast.next is null), the slow pointer will be at the middle of the linked list.

Reverse linked list operation

prev = null
current = head
while current is not null:
    next = current.next
    current.next = prev
    prev = current
    currnet = nextprev is head of the reversed linked list

Graphical Explanation

step1: find the middle of the linked list
step2: reverse the second half of the linked list
step3: check if node’s value in the first and second half of the linked list are matched one by one