[Ninja Algorithm] From Life Scenes to Pastoral Links: Exploring Symmetry Detection

From life scenes to palindrome link list: Exploring symmetry detection

Palindrome phenomenon in life

In daily life, palindromes are everywhere. For example, "Shanghai tap water comes from the sea" and "12321" strings or numbers that are the same as those that are reading in a straight and backward are palindromes. By extending this concept to the linked list, we get the palindromic link list problem we want to discuss today: whether the results of a linked list read from front to back and read from back to front are the same.

Problem description

LeetCode Question 234 "Pastoral Link List" requirements: Give you a head of a single linked list, please determine whether the linked list is a pastoral link.

For example:

Enter: 1 → 2 → 2 → 1
 Output: true

 Enter: 1 → 2 → 3 → 2 → 1
 Output: true

 Enter: 1 → 2 → 3 → 3 → 1
 Output: false

Basic knowledge preparation

The core of this question is to use the "reversal link list" we have learned before. If you are not familiar with the reversal of linked lists, it is recommended to review the previous article first. Remember, linked list inversion is a cornerstone, and here we want to use it to solve more complex problems.

Intuitive solution: convert to array

The simplest idea is to convert the linked list into an array, and then use a double pointer to move from both ends to the middle to compare. It's like spreading a stack of playing cards on the table and comparing whether each card is the same from both ends.

Array method implementation

public boolean isPalindrome(ListNode head) {
     List<Integer> vals = new ArrayList<>();
    
     // Copy the linked list value into the array
     ListNode current = head;
     while (current != null) {
         ();
         current = ;
     }
    
     // Use double pointers to determine whether to go back
     int left = 0, right = () - 1;
     while (left < right) {
         if (!(left).equals((right))) {
             return false;
         }
         left++;
         right--;
     }
    
     return true;
 }

Optimization solution: Invert the second half

If you think about it carefully, we don't actually need extra arrays. This clever method can be used:

Find the midpoint of the linked list
Reversal the latter half
Compare whether the two halves are the same
(Optional) Restore the original state of the linked list

It's like dividing a stack of cards in half, turning the second half upside down, and comparing them one by one.

Find the midpoint: Fast and Slow Pointer Method

Imagine two people running on the track, one is twice as fast as the other. When the fast runner reaches the finish line, the jogger is just at the midpoint!

Detailed code implementation

public boolean isPalindrome(ListNode head) {
     if (head == null || == null) {
         return true;
     }
    
     // Step 1: Find the midpoint
     ListNode slow = head;
     ListNode fast = head;
     while ( != null && != null) {
         slow = ;
         fast = ;
     }
    
     // Step 2: Reverse the latter half
     ListNode secondHalf = reverseList();
    
     // Step 3: Compare whether the two halves are the same
     ListNode firstHalf = head;
     ListNode temp = secondHalf; // Save the start position, used for later recovery
     boolean result = true;
     while (secondHalf != null) {
         if ( != ) {
             result = false;
             break;
         }
         firstHalf = ;
         secondHalf = ;
     }
    
     // Step 4: Recover the linked list (optional)
      = reverseList(temp);
    
     return result;
 }

 // Linked list inversion function (using the method we learned before)
 private ListNode reverseList(ListNode head) {
     ListNode prev = null;
     ListNode curr = head;
     while (curr != null) {
         ListNode nextTemp = ;
          = prev;
         prev = curr;
         curr = nextTemp;
     }
     return prev;
 }

Graphical process

Take 1→2→3→2→1 as an example:

1) Initial status:
 1 → 2 → 3 → 2 → 1

 2) Find the midpoint:
 1 → 2 → [3] → 2 → 1
 slow points to 3

 3) Reverse the second half:
 1 → 2 → 3 ← 2 ← 1

 4) Compare the two halves:
 (1 → 2) and (1 → 2) Compare

 5) Restore to its original state:
 1 → 2 → 3 → 2 → 1

Complexity analysis

Space optimization solution:

Time complexity: O(n)
Space complexity: O(1), only a few pointers are used
Advantages: High space efficiency and elegant thinking
Disadvantages: Modified the original linked list structure (although it was restored in the end)

Summary of important ways of thinking

Problem transformation: Convert palindrome judgment into symmetry comparison
Space optimization thinking：
- No extra array storage
- Use the original space to operate
Step by step thought：
- Find the midpoint (fast and slow pointer)
- Reversal the second half (link list inversion)
- Comparison (double pointer)
- Recover (reverse again)
Boundary processing：
- Empty link table
- Single node link table
- Processing of even/odd lengths

Summary of practical skills

Key points to solving similar problems:

Proficient in basic operations (such as reversal of linked lists)
Use fast and slow pointers to find the midpoint
Consider the possibility of space optimization
Pay attention to protecting the original data structure

Related thinking training:

Judgment of number of palindromes
The problem of substrings of the script
Problems with mid-points of linked list
Various variants of linked list inversion

summary

The palindromic linked list problem is a good example, showing how to combine basic algorithms (such as linked list inversion, fast and slow pointers) to solve more complex problems. It teaches us:

The importance of basic algorithms
Space optimization thinking style
Methods for decomposing problems
The elegance of the code

Next time you encounter a similar symmetry judgment problem, don’t rush to use extra space and think about whether you can solve the problem by changing the data structure itself!

Author: Ninja Algorithm
Official account: Ninja Algorithm

I have prepared a list of questions to practice and detailed questions for these questions, covering most common interview questions. I can say responsibly that as long as you truly master these questions, 80% of the algorithm interviews will encounter similar questions. Reply to the official account [Question List] to obtain ~

[Ninja Algorithm] From Life Scenes to Pastoral Links: Exploring Symmetry Detection | LeetCode 234 Pastoral Links