leetcode 328. Odd Even Linked List

 

ListNode 에서 홀수 index, 짝수 index를 뽑아서 짝수 index는 순서대로 뒤로 나열하는 문제다.

 

우선 홀짝을 순서대로 뽑아보자

class Solution {
    public ListNode oddEvenList(ListNode head) {
        ListNode odd = head;
        ListNode even = head.next;
    }
}

 

이렇게 초기화를 한 상태에서 head.next가 없을때까지 돌려야할것같은데..

우선 홀-짝-홀-짝 이런순서로 가니까 무조건 짝이 뒤에올것이기때문에 while문에 조건을 넣어줬다.

 

class Solution {
    public ListNode oddEvenList(ListNode head) {
        ListNode odd = head;
        ListNode even = head.next;
        
        while (even != null) {
            odd = odd.next.next;
            even = even.next.next;
            
            odd = odd.next;
            even = even.next;
        }
    }
}

 

이렇게되면 even에는 .next.next를 넣었으니, even= even.next 를 실행했을때 next값이 null 이라면 while문은 돌지않을것이다.

그런데 

 

1 -> 2 -> 3 -> 4 -> 5

 

예시가 있다고 하자.

 

while 문 돌기전에 odd = 1, even = 2

 

첫번째 while 문에서

odd = 3, odd.next = 5

even = 4, even.next = null 이다.

 

두번째 while문에서 odd = 5, even = null 이기때문에 nullpointException 발생한다.

따라서 while문을 수정해주자.

class Solution {
    public ListNode oddEvenList(ListNode head) {
        ListNode odd = head;
        ListNode even = head.next;
        
        while (even != null && even.next != null) {
            odd = odd.next.next;
            even = even.next.next;
            
            odd = odd.next;
            even = even.next;
        }
    }
}

이렇게하면 비록 두번째 루프는 돌지않았지만, odd.next를 설정했으므로 odd의 세팅이 완료된다.

 

그리고 최종적으로 기존의 odd 뒤에 even을 붙여준다.

class Solution {
    public ListNode oddEvenList(ListNode head) {
        ListNode odd = head;
        ListNode even = head.next;
        
        while (even != null && even.next != null) {
            odd = odd.next.next;
            even = even.next.next;
            
            odd = odd.next;
            even = even.next;
        }
        odd.next = even;
        
        return head;
    }
}

 

그리고 최종적으로 return 은 head를 해준다.

왜냐하면 odd를 return 하면 odd의 시작점을 알수없기때문~

 

마지막으로 null 예외케이스를 넣어주면

class Solution {
    public ListNode oddEvenList(ListNode head) {
    
    	if (head == null) return null;
        
        ListNode odd = head;
        ListNode even = head.next;
        
        while (even != null && even.next != null) {
            odd = odd.next.next;
            even = even.next.next;
            
            odd = odd.next;
            even = even.next;
        }
        odd.next = even;
        
        return head;
    }
}