[Go] Linked List - Odd Even Linked List

Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list.

The first node is considered odd, and the second node is even, and so on.

Note that the relative order inside both the even and odd groups should remain as it was in the input.

You must solve the problem in O(1) extra space complexity and O(n) time complexity.

 

Example 1:

Input: head = [1,2,3,4,5]
Output: [1,3,5,2,4]

Example 2:

Input: head = [2,1,3,5,6,4,7]
Output: [2,3,6,7,1,5,4]

 

Constraints:

• The number of nodes in the linked list is in the range [0, 104].
• -106 <= Node.val <= 106

My code

func oddEvenList(head *ListNode) *ListNode {
	var odd *ListNode
	var even *ListNode
	var e *ListNode

	if head != nil {
		odd = head
		even, e = head.Next, head.Next
	} else {
		return head
	}

	for odd != nil && even != nil && odd.Next != nil && even.Next != nil {
		odd.Next = even.Next
		odd = odd.Next
		even.Next = odd.Next
		even = even.Next
	}
	odd.Next = e
	return head
}

https://go.dev/play/p/_laRQXpqGBH

• head address must be hold by odd, even and even head.
• if head is not nil, odd, even, e will have head, head.next, if not return nil.
• for loop will check odd, even, odd.Next, even Next are not nil.
• after finishing for loop, odd.Next will have e(even head)
• and return head.

sample 0 ms submission & samp,e 3200 KB submission

func oddEvenList(head *ListNode) *ListNode {
    if head ==nil {return nil}
    odd := head
    even := head.Next
    evenHead := head.Next
    
    for even!=nil && even.Next!=nil {
        // put odd to odd list
        odd.Next = odd.Next.Next
        // put even to even list
        even.Next = even.Next.Next
        
        // move to next for both odd and even
        odd = odd.Next
        even = even.Next
    }
    // put even after odd
    odd.Next = evenHead
    return head
}

sample 1 ms submission

func oddEvenList(head *ListNode) *ListNode {
    if head == nil {
        return head
    }
    a := head
    b := head.Next
    es := b
    
    for b != nil && b.Next != nil {
        a.Next = b.Next
        b.Next = b.Next.Next
        if a.Next != nil {
            a = a.Next
        }
        b = b.Next
    }
    a.Next = es
    return head
}

sample 2 ms submission

func oddEvenList(head *ListNode) *ListNode {
	if head == nil {
		return nil
	}

	var odd, even = head, head.Next
	var evenHead = even

	for even != nil && even.Next != nil {
		odd.Next = even.Next
		odd = odd.Next

		even.Next = odd.Next
		even = even.Next
	}

	// Append all even list at the end of odd list
	odd.Next = evenHead

	return head
}

sample 3 ms submission & sample 3300 KB submission

func oddEvenList(head *ListNode) *ListNode {
	if head == nil {
		return head
	}

	odd := head
	even := head.Next
	evenHead := even // just to keep track of where even-node list starts

	for even != nil && even.Next != nil {
		odd.Next = odd.Next.Next
		odd = odd.Next
		even.Next = even.Next.Next
		even = even.Next
	}

  odd.Next = evenHead

  return head
}

sample 4 ms submission

func oddEvenList(head *ListNode) *ListNode {
    var eHead, oHead *ListNode
	var odds, evens *ListNode = &ListNode{Val: -1}, &ListNode{Val: -1}
    idx := 0
	for head != nil {

		if idx%2 == 0 {
			//even
			if eHead == nil {
				eHead = head
			}
			evens.Next, evens = head, head
		} else {
			if oHead == nil {
				oHead = head
			}
			odds.Next, odds = head, head
		}

		head = head.Next
		idx++
	}

	//merge the two list
	evens.Next, odds.Next = oHead, nil
	return eHead
}

sample 5 ms submission

func oddEvenList(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }
    var headEven *ListNode = head.Next
    even := head.Next
    odd := head

    for (even != nil && even.Next != nil) {
        odd.Next = odd.Next.Next
        even.Next = even.Next.Next
        even = even.Next
        odd = odd.Next

    }
    odd.Next = headEven
    return head
}

sample 6 ms submission

func oddEvenList(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }
    var even *ListNode = &ListNode{Next: head}

    odd := head
    // even := head.Next
    curEven := even
    for (odd != nil && odd.Next != nil) {
        even.Next = even.Next.Next
        odd.Next = odd.Next.Next
        even = even.Next
        odd = odd.Next

    }
    even.Next = nil
    
    curOdd := head
    for(curOdd.Next != nil) {
        curOdd = curOdd.Next
    }
    
    curOdd.Next = curEven.Next
    return head
}

sample 3400 KB submission

func oddEvenList(head *ListNode) *ListNode {
    
    if head == nil || head.Next == nil {
        return head
    }
      
    odd := head
    even := head.Next
    evenHead := head.Next
    
    for even != nil  && even.Next != nil {
        odd.Next = even.Next
        odd = even.Next
        even.Next = odd.Next
        even = even.Next
        
    }
    
    odd.Next = evenHead
    
    return head
    
}