How to check if linked list is palindrome?

[Question]: Input singly linked list return true if linked list is palindrome.
Example: –

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

Approach# Reverse Linked list & compare first and last item

func reverseList2(_ head: ListNode?) -> ListNode? {
     if head == nil || head?.next == nil {
         return head
     }
     let newHead = reverseList2(head?.next)
     let nextNode = head?.next
     nextNode?.next = head
     head?.next = nil
     return newHead
 }
 
 func isPalindrome(_ head: ListNode?) -> Bool {
     if head == nil {
         return true
     }
     var headCopy = head
     var middleNode = findMiddle(head)
     middleNode = reverseList2(middleNode)
     while middleNode != nil {
         if headCopy?.val != middleNode?.val {
             return false
         }
         headCopy = headCopy?.next
         middleNode = middleNode?.next
     }
     return true
 }

 func findMiddle(_ head: ListNode?) -> ListNode? {
     var slow = head, fast = head
     while fast?.next != nil && fast != nil {
         slow = slow?.next
         fast = fast?.next?.next
     }
     return slow
 }

var palindromeLinkedList = ListNode(5, ListNode(1, ListNode(10,ListNode(1, ListNode(5)))))
let isPalindrom = isPalindrome(palindromeLinkedList)
//print("LinkList isPalindrom --- ", isPalindrom) // true

Leave a Comment

Your email address will not be published. Required fields are marked *