Swift version with full comments


  • 0
    S
    class Solution {
        func isPalindrome(_ head: ListNode?) -> Bool {
            // use a step runner twice to detect the end of the linked list
            // reversing as we step through current to the middle
            // when runner hits the end, run current in forward and
            // reverse directions and check for equality 
            
            var current: ListNode? = head
            var runner: ListNode? = head
            var reverse: ListNode? = nil
            
            while runner != nil && runner?.next != nil {
                // run the runner
                runner = runner?.next?.next
    
                // reverse the current
                let temp: ListNode? = reverse
                reverse = current
                
                // we mutate current below, so 
                // walk the current first
                current = current?.next
                
                // reverse is pointing to the old current,
                // set it's new next
                reverse?.next = temp
            }
    
            // if we have an odd number of nodes, we need to walk
            // current one more time to get to the mid point of the list
            if runner != nil {
                current = current?.next
            }
            
            // middle out check for equality
            while reverse != nil {
                if current?.val != reverse?.val {
                    return false
                }
                current = current?.next
                reverse = reverse?.next
            }
         
            return true
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.