Golang solution using two pointers


  • 0

    Using two pointers, slow (proceed by 1) and fast (proceed by 2), and slow pointer will reverse the list while proceeding.

    func isPalindrome(head *ListNode) bool {
    	if head == nil || head.Next == nil {
    		return true
    	}
    
    	single, double := head, head
    	var prev, prev2 *ListNode
    	for {
    		double = double.Next.Next
    
    		// single node reverses its previous list
    		prev = single
    		single = single.Next
    		prev.Next = prev2
    		prev2 = prev
    
    		if double == nil || double.Next == nil {
    			break
    		}
    	}
    
    	left, right := prev, single
    	if double != nil { // adjust needed a number of nodes is even
    		right = right.Next
    	}
    
    	for left != nil && right != nil {
    		if left.Val != right.Val {
    			return false
    		}
    		left, right = left.Next, right.Next
    	}
    	return true
    }
    

Log in to reply
 

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