🎉 Yay! DSA-30 is now live!
Day 3 - Linked Lists
Practice Questions
Palindrome Linked List

Palindrome Linked List

Description

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

Constraints

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

Test Cases

  • Input: head = [1,2,2,1]
    Output: true

  • Input: [1, 2]
    Output: false

Code

Approach 1: Using an Array or a Vector

Explanation

  1. Traverse the linked list and store the values in an array or a vector.
  2. Use two pointers, one at the start and the other at the end of the array.
  3. If the values at the two pointers are not equal, return false.
  4. If the loop completes, return true.

Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(n)
Approach 2: Using fast and slow pointers

Explanation

  1. Use two pointers, one slow and one fast.
  2. Traverse the linked list using the fast pointer, and move the slow pointer to the middle of the linked list.
  3. Reverse the second half of the linked list.
  4. Traverse the first half and the reversed second half of the linked list and check if the values are equal.
  5. If the loop completes, return true.

Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(1)
Reverse a Linked ListTODO