[LeetCode] Odd Even Linked List

Odd Even Linked List - LeetCode

문제 이해

무슨 말이지? 문제이해를 잘 못 할 뻔 했다.

처음에는 노드 내부의 값이 홀수 인것, 짝수인것들을 모아서 그룹을 지으라는 줄 알았는데 그게 아닌 것 같다.

문제의 예시를 보니, index 가 홀수인 것을 그룹핑, index가 짝수인것을 그룹지으라는 말이었다.

문제 풀이

단일 연결 리스트 문제다.

따라서 앞에서부터 순차적으로 탐색을 진행한다.

프로그래밍에서 index는 0부터시작하는게 국룰이지만, 일단 여기서는 1부터 시작하는 것으로 하겠다.

단순하게 푼다면???

그냥, 순차적으로 탐색하면서, array에다가 담고나서

다시 array에서 홀수들만을 이용해서 ListNode를 만들고

기존의 것을 최대한 활용해 본다면???

ListNode even;
ListNode odd; 
// 이 둘을 두고 시작한다. 

• index가 홀수이면, odd에 더하고,
• index가 짝수이면 even에 더한다.
• 이 때, 현재 노드와 다음 노드간의 연결을 끊어줘야 하기 때문에
  • 다음 노드를 보관(reserve)해 놓고
  • 현재 노드를 odd 또는 even에 연결시킨다.
  • 그리고 현재노드는, 보관했던 노드로 업데이트한다.
• 현재 내 코드는, 매번 cur 노드와 next 노드사이의 연결을 끊는 operation이 들어갔다.

class Solution {
    public ListNode oddEvenList(ListNode head) {
        // 길이가 2이하인 리스트라면 그대로 리턴
        if (head == null || head.next == null || head.next.next==null) return head;
        // 나중에 even과 odd를 이어붙일 수 있을까? 여기서도 dummy node를 사용해야할듯
        ListNode cur = head;
        ListNode evenDummy = new ListNode(0);
        ListNode even = evenDummy;
        ListNode oddDummy = new ListNode(0);
        ListNode odd = oddDummy;
        int cnt = 1;
        ListNode reserved = null;
        while(cur != null){
            // 다음 노드를 reserve
            reserved = cur.next;
            // 현재 노드와 다음 노드의 연결을 끊는다
            cur.next = null;
            // 현재노드를 리스트에 연결
            // 짝수 인 경우
            if (cnt % 2 == 0){
                even.next = cur;
                even = even.next;
            }else{
                odd.next = cur;
                odd = odd.next;
            }
            // 다음 노드로 업데이트
            cur = reserved;
            cnt++;
        }
        odd.next = evenDummy.next;
        return oddDummy.next;
    }
}

개선시키는 방법 ( 다른 사람의 코드 )

비슷한 로직인 것 같은데 100%인 사람이 있어서 코드를 살펴봤다.

• 나는 더미노드에 사로잡혀 있었다.

head와 tail을 두고

• 처음 추가하는 노드에 대해서만, head 를 세팅하고
• 나머지에 대해서는 tail을 업데이트 하면 됐다.

class Solution {
    public ListNode oddEvenList(ListNode head) {
       // 길이가 1이하인 리스트라면 그대로 리턴
               if(head==null || head.next==null) return head;
        
        ListNode oddHead = null, oddTail = null;
        ListNode evenHead = null, evenTail = null;
        ListNode curr = head;
        int i = 1;
        while(curr!=null){
			// 홀수 
            if(i%2==1){
								// 홀수 리스트에 처음으로 더해주는 경우
                if(oddHead==null){
                    oddHead = curr;
                    oddTail = curr;
                }
                else{
                    oddTail.next = curr;
                    oddTail = oddTail.next;
                }
            }
			// 짝수
            else{
****								// 짝수 리스트에 처음으로 더해주는 경우
                if(evenHead==null){
                    evenHead = curr;
                    evenTail = curr;
                }
                else{
                    evenTail.next = curr;
                    evenTail = evenTail.next;
                }
            }
            curr = curr.next;
            i++;
        }
        
        evenTail.next = null;     // 짝수노드의 next를 null로 업데이트 하지 않으면 cycle 위험
        oddTail.next  = evenHead;   // 둘을 합해줌
        return oddHead;
    }
}

이문제는 비슷비슷한데 미묘하게 시간복잡도와 공간복잡도가 갈리는 것 같다.

이쯤만 해두기로 하였음.