check if linked list is palindrome or not - swift

Swift – Check If Linked List is Palindrome or Not.

(Last Updated On: September 27, 2021)

In this challenge, we will be checking whether a given linked list is palindrome or not.

For starters, you can copy the Linked List from the post Linked List in Swift if you don’t already have the Linked List created in your playground.

Once you have copied the code to the playground, let’s jump right into the question.

palindrome is a word, number, phrase, or other sequence of characters which reads the same backward as forward, such as madam or racecar

Wikipedia

To check for a linked list is palindrome or not, we need to check whether the linked list returns the same values when read from head to tail and tail to head.

While there may be other ways to do it, I came up with an idea to create a new linked list which is the reverse of the given linked list and then compare both the lists until list.value != newList.value

Let’s jump into the code and see how it works.

First let’s create a linked list and add data to it.

//1
var list = LinkedList<Int>()

//2
func addDataToList() {
    list.append(1)
    list.append(1)
    list.append(0)
    list.append(0)
    list.append(1)
    list.append(1)

}

addDataToList()

Now let’s write the function to check for palindrome.

func checkPalindrome<T : Equatable>(list : LinkedList<T>) -> Bool {
    //1
    var newList = LinkedList<T>()
    var current = list.head
    var isPalindrome = false
    //2 check if list not empty
    guard list.head != nil else {
        return false
    }

    //3 if only one element then it is a palindrome
    guard list.head?.next != nil else {
        return true
    }

    //4 if many elements

    while current != nil {
        newList.push(current!.value)
        current = current?.next
    }

    //5 check if equal

    var listIndex = list.head
    var newListIndex = newList.head

    while listIndex != nil {
        if listIndex?.value == newListIndex?.value {
            isPalindrome = true
        } else {
            return false
        }
        listIndex = listIndex?.next
        newListIndex = newListIndex?.next

    }
    //6
    print("OLD LIST:", list)
    print("NEW LIST:", newList)
    print("Palindrome: ", isPalindrome)


    return isPalindrome
}

Now let’s go to each point one by one.

  1. First we create a newList in which we will store the reverse of the linked list. We declare a variable current to store the position of linked list for traversing it. We also created a Bool variable that will store whether list is palindrome or not.
  2. Check if linked list is not empty. If it is, return nil.
  3. Check if linked list only contains one element. Return true as reverse of single node always would be the node itself.
  4. Now we traverse the linked list and append the nodes of the list to the new list. NOTE: The append function is a head-end insertion. It will traverse the list and append the elements of the list to the beginning of the newList. You can check the append function in the LinkedList.Swift to understand better.
  5. Now we traverse again through the list and this time we compare both the linked list by their current node values. If the values are same, keep traversing the list until the end. If the values are different, return from the function.
  6. Finally print the old and new list and whether the linked list is palindrome or not.
// OUTPUT

OLD LIST: 1 --> 1 --> 0 --> 0 --> 1 --> 1     
NEW LIST: 1 --> 1 --> 0 --> 0 --> 1 --> 1     
Palindrome:  true

You can see the output is true as the list reads the same from backward as well as forward. Hence it is a Palindrome.

There are many other ways to implement the same, if you come up with a better solution, let me know in the comments.

Leave a Comment