[LeetCode] 328. Odd Even Linked List (C#)

https://leetcode.com/problems/odd-even-linked-list/description/

 

 

 

홀수번째 Node를 앞으로 당겨오고, 짝수번째 Node를 뒤로 밀어주는 문제.

 

제한 사항

• 공간 복잡도 : O(1)
• 시간 복잡도 : O(N)

 

1. 풀이

• 더 이상 Odd 노드가 없을 때까지 Odd는 Odd끼리, Even은 Even끼리 연결
• 마지막에 Odd의 tail과 Even의 head를 연결

namespace PS.LeetCode;

public class Solution_328_1
{
    public class ListNode
    {
        public int val;
        public ListNode next;

        public ListNode(int val = 0, ListNode next = null)
        {
            this.val = val;
            this.next = next;
        }
    }
    
    public ListNode OddEvenList(ListNode head)
    {
        if (head == null)
        {
            return head;
        }
        
        var oddNode = head;
        var evenHead = head.next;
        
        while (oddNode.next?.next != null)
        {
            var evenNode = oddNode.next;
            oddNode.next = oddNode.next.next;
            evenNode.next = oddNode.next.next;
            oddNode = oddNode.next;
        }

        oddNode.next = evenHead;
        
        return head;
    }
}