Odd Even Linked List

Problem: Given a singly linked list, group all nodes at odd position together followed by the nodes at even position.

Example:

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

Approach: It is a straight forward problem to solve. Not much to explain about the approach here as you can understand the approach by just looking at the code.

Implementation in C#:

        public ListNode OddEvenList(ListNode head)

    {

        if (head == null || head.next == null)

        {

            return head;

        }

        ListNode odd = head, even = head.next;

        ListNode evenHead = even;

        while (even != null)

        {

            odd.next = even.next;

            if (odd.next != null)

            {

                odd = odd.next;

            }

            even.next = odd.next;

            even = even.next;

        }

        odd.next = evenHead;

        return head;

    }

Complexity: O(n)