[Go] Linked List - Palindrome Linked List

Given the head of a singly linked list, return true if it is a palindrome.

 

Example 1:

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

Example 2:

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

 

Constraints:

• The number of nodes in the list is in the range [1, 105].
• 0 <= Node.val <= 9

 

Follow up: Could you do it in O(n) time and O(1) space?

 

My code

func isPalindrome(head *ListNode) bool {
	count := 0

	node := head
	palindrome := []int{}

	for node != nil {
		palindrome = append(palindrome, node.Val)
		count++
		node = node.Next
	}
	if count == 1 {
		return true
	}

	mid := count / 2
	lp, rp := 0, 0
	if count%2 != 0 {
		lp, rp = mid-1, mid+1
	} else {
		lp, rp = mid-1, mid
	}
	for lp >= 0 && rp < count {
		if palindrome[lp] != palindrome[rp] {
			return false
		}
		lp--
		rp++

	}
	return true
}

https://go.dev/play/p/8ywf452RzZa

• I don't have any idea for better algorithm.
• Add values to slice in sequence.
• count will be used for pointer.
• if condition will check count is odd or even.
• for loop will check slice has palindrome or not.

sample 120 ms submission

func isPalindrome(head *ListNode) bool {
	temp := head
	length := 0
	for temp != nil {
		length += 1
		temp = temp.Next
	}
	tempArray := make([]int, length, length)
	count := 0
	for head != nil {
		tempArray[count] = head.Val
		head = head.Next
        count++
	}
	for count = 0; count < length/2; count++ {
		if tempArray[count] != tempArray[length-1-count] {
			return false
		}
	}
	return true
}

• I think this code is not efficient. because it checkes length of linked list and again loads values for adding to slice.

sample 124 ms submission

func isPalindrome(head *ListNode) bool {
    var array [100000]int
    i := 0
    
    for head != nil {
        array[i] = head.Val
        i++
        head = head.Next
    }
    i--
    if i == 1{
        return array[0] == array[1]
    }
    
    //[1,1,2,1],  i =3
    for j:=0; j<=int(i/2); j++ {
        if (array[j] != array[i-j]){
            return false
        }
    }

    return true
}

sample 128 ms submission

func isPalindrome(head *ListNode) bool {
    slow, fast := head, head  
    
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    
    var prev *ListNode
    for slow != nil {
        tmp := slow.Next
        slow.Next = prev
        prev = slow
        slow = tmp
    }
    
    for prev != nil && head != nil {
        if prev.Val != head.Val {
            return false
        }
        prev = prev.Next
        head = head.Next
    }
           
    return true
}

• First for loop will make slow pointer to point mid when fast reachs to end nil.
• Second for loop will make prev to have reversed linked list.
• Third for loop will check reversed val and head val.

sample 130 ms submission

func isPalindrome(head *ListNode) bool {
    var slow, fast *ListNode = head, head
    for fast != nil && fast.Next != nil{
        slow = slow.Next
        fast = fast.Next.Next
    }
    var cur, prev , next *ListNode = slow, nil, nil
    for cur != nil{
        next = cur.Next
        cur.Next = prev
        prev = cur
        cur = next
    }
    for prev != nil{
        if head.Val != prev.Val{
            return false
        }
        head = head.Next
        prev = prev.Next
    }
    return true
}

sample 131 ms submission

func isPalindrome(head *ListNode) bool {
    middleNode := getMiddleNode(head)
    secondHalfHead := reverse(middleNode.Next)
    
    p1 := head
    p2 := secondHalfHead
    
    for p2 != nil{
        if p1.Val != p2.Val {
            return false
        }
        p1 = p1.Next
        p2 = p2.Next
    }
    
    return true
}

func getMiddleNode(head *ListNode) *ListNode{
    first := head
    slow := head
    for first.Next != nil && first.Next.Next != nil{
        first = first.Next.Next
        slow = slow.Next
    }
    return slow
}

func reverse(head *ListNode) *ListNode {
    var prev *ListNode
    curr := head
    for curr != nil{
        next := curr.Next
        curr.Next = prev
        prev = curr
        curr = next
    }
    return prev
}

sample 132 ms submission & sample 9000 KB submission

func isPalindrome(head *ListNode) bool {
    var slow, fast *ListNode = head, head
    for fast != nil && fast.Next != nil{
        slow = slow.Next
        fast = fast.Next.Next
    }
    var cur, prev , next *ListNode = slow, nil, nil
    for cur != nil{
        next = cur.Next
        cur.Next = prev
        prev = cur
        cur = next
    }
    for prev != nil{
        if head.Val != prev.Val{
            return false
        }
        head = head.Next
        prev = prev.Next
    }
    return true
}

sample 133 ms submission

func isPalindrome(head *ListNode) bool {
    numNode := 0
    headNode := head
    for head != nil{
        numNode++
        head = head.Next
    }
    head = headNode
    //If one node return true 
    if numNode == 1{
        return true 
    }   

    centerNode := numNode/2 + numNode % 2 + 1
    var prevNode *ListNode
    nodeCount := 1
    
    for nodeCount != centerNode{
        nextNode := head.Next
        head.Next = prevNode
        prevNode = head
        head = nextNode
        nodeCount++
    }
    if numNode % 2 == 1{
        prevNode = prevNode.Next
    }
    
    for(head.Next != nil && head.Val == prevNode.Val){
        head = head.Next
        //Going backwards
        prevNode = prevNode.Next
    }
    if head.Val == prevNode.Val{
        return true
    } else {
        return false 
    }

sample 134 ms submission

func isPalindrome(head *ListNode) bool {
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    if fast != nil {
        slow = slow.Next
    }
    newHead := reverse(slow)
    left, right := head, newHead
    for right != nil {
        if left.Val != right.Val {
            return false
        }
        left = left.Next
        right = right.Next
    }
    return true
}

func reverse(head *ListNode) *ListNode {
    var pre *ListNode = nil
    cur, next := head, head
    for cur != nil {
        next = cur.Next
        cur.Next = pre
        pre = cur
        cur = next
    }
    return pre
}

sample 135 ms submission

func isPalindrome(head *ListNode) bool {
    arr := []int{}
    for head != nil {
        arr = append(arr, head.Val)
        head = head.Next
    }
    
    size := len(arr)
    for i:=0 ; i<len(arr)/2 ; i++{
        if arr[i] != arr[size-1-i]{
            return false
        }
    }
    return true
}

sample 136 ms submission

func isPalindrome(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return true
    }
    // Find the middle of the list
    var prev *ListNode
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        prev = slow
        slow = slow.Next
        fast = fast.Next.Next
    }
    // Split list in two
    prev.Next = nil
    // Reverse the second half
    slow = reverse(slow)
    // Compare both halves
    current := head
    for current != nil {
        if current.Val != slow.Val {
            return false
        }
        current = current.Next
        slow = slow.Next
    }
    return true;
}

func reverse(head *ListNode) *ListNode {
    var prev, next *ListNode
    current := head
    for current != nil {
        next, current.Next = current.Next, prev
        prev, current = current, next
    }
    return prev
}

sample 8300 KB submission

func isPalindrome(head *ListNode) bool {
    if head == nil {
        return false
    }
    size := 0
    
    // Count the length
    node := head
    for node != nil {
        size++
        node = node.Next
    }
    
    if size == 1 {
        return true
    }
    
    // Skip to the halfway point
    stackSize := size/2
    
    isOddStackSize := size % 2 == 1
    
    stack := make([]int, stackSize)
    node = head
    for i:=0; i<stackSize; i++ {
        stack[stackSize-i-1] = node.Val
        node = node.Next
    }
    
    if isOddStackSize {
        node = node.Next
    }
    
    i := 0
    for node != nil {
        if stack[i] != node.Val {
            return false
        }
        node = node.Next
        i++
    }
    return true
}

sample 8400 KB submission

func isPalindrome(head *ListNode) bool {
    tmp := head
    count := 0
    for tmp != nil {
        count++
        tmp = tmp.Next
    }
    mid := head
    a := make([]int,count/2)
    i:= 0
    for i < count/2 {
        a[i] = mid.Val
        mid = mid.Next
        i++
    }
    if count % 2 != 0 {
        mid = mid.Next //skipping for odd no
    }
    for mid != nil {
        if a[i-1] != mid.Val {
            return false
        }
        mid = mid.Next
        i--
    }
    return true
}

sample 8500 KB submission

func reverse(head *ListNode) *ListNode {
    t := head
    for t.Next != nil {
        t.Next.Next, t.Next, head = head, t.Next.Next, t.Next
    }
    return head
}

func isPalindrome(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return true
    }
    m, f := head, head
    for f != nil {
        m, f = m.Next, f.Next
        if f == nil {
            break
        }
        f = f.Next
    }
	sh := reverse(m)
	defer reverse(sh)
	for f, s := head, sh; s != nil; f, s = f.Next, s.Next {
		if f.Val != s.Val {
			return false
		}
	}
    return true
}

sample 8600 KB submission

func isPalindrome(head *ListNode) bool {
    if head == nil {
        return false
    }
    opt := head
    length := 0
    for opt != nil {
        length++
        opt = opt.Next
    }
    arr := make([]*ListNode, length/2)
    opt = head
    for i := 0; i < length/2;i++ {
        opt = opt.Next
    }
    if length%2 != 0 {
        opt = opt.Next
    }
     for i := 0; i < length/2;i++ {
         arr[i] = opt
         opt = opt.Next
    }
    for i:=len(arr)-1;i>=0;i-- {
        if head.Val != arr[i].Val {
            return false
        }
        head = head.Next
    }
    return true
}

sample 8800 KB submission

func isPalindrome(head *ListNode) bool {
    //find midpoint
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    
    //reverse the 2nd part of list
    var prev *ListNode
    for slow != nil {
        next := slow.Next
        slow.Next = prev
        prev = slow
        slow = next
    }
    
    //compare both of sublist
    left,right := head,prev
    for right != nil {
        if left.Val != right.Val {
            return false
        }
        left = left.Next
        right = right.Next
    }
    return true
}

sample 8900 KB submission

func isPalindrome(head *ListNode) bool {
	if head.Next == nil {
		return true
	}

	var tmp, fast, slow *ListNode
	fast = head
	slow = head
	tmp = nil

	for fast != nil && fast.Next != nil {
		fast = fast.Next.Next
		slow.Next, slow, tmp = tmp, slow.Next, slow
	}

	if fast == nil {
		fast = slow
	} else {
		fast = slow.Next
	}
	tmp, slow = slow, tmp

	isPlndrm := true
	for fast != nil && slow != nil {
		// fmt.Println(fast.Val, "-", slow.Val)
		isPlndrm = isPlndrm && fast.Val == slow.Val
		fast = fast.Next
		slow.Next, slow, tmp = tmp, slow.Next, slow
	}
	return isPlndrm
}

sample 9000 KB submission

func isPalindrome(head *ListNode) bool {
    var slow, fast *ListNode = head, head
    for fast != nil && fast.Next != nil{
        slow = slow.Next
        fast = fast.Next.Next
    }
    var cur, prev , next *ListNode = slow, nil, nil
    for cur != nil{
        next = cur.Next
        cur.Next = prev
        prev = cur
        cur = next
    }
    for prev != nil{
        if head.Val != prev.Val{
            return false
        }
        head = head.Next
        prev = prev.Next
    }
    return true
}