328. Odd Even Linked List

Problem

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

Example 1:

Input: 1->2->3->4->5->NULL
Output: 1->3->5->2->4->NULL

Example 2:

Input: 2->1->3->5->6->4->7->NULL
Output: 2->3->6->7->1->5->4->NULL

Note:

• The relative order inside both the even and odd groups should remain as it was in the input.
• The first node is considered odd, the second node even and so on ...

Problem Summary

This problem is very similar to Problem 86. Problem 86 puts the smaller values that come before a certain point into one linked list, and the larger values that come after a certain point into another linked list. Finally, concatenating the two linked lists head-to-tail gives the answer.

Solution Approach

The idea for this problem is the same: put the odd-numbered nodes and even-numbered nodes into two linked lists respectively, then concatenate them head-to-tail at the end to get the answer.

Code

package leetcode

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func oddEvenList(head *ListNode) *ListNode {
	oddHead := &ListNode{Val: 0, Next: nil}
	odd := oddHead
	evenHead := &ListNode{Val: 0, Next: nil}
	even := evenHead

	count := 1
	for head != nil {
		if count%2 == 1 {
			odd.Next = head
			odd = odd.Next
		} else {
			even.Next = head
			even = even.Next
		}
		head = head.Next
		count++
	}
	even.Next = nil
	odd.Next = evenHead.Next
	return oddHead.Next
}