[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