[LeetCode] 328. Odd Even Linked List - 구현(Implementation) + 아이디어(Idea) JAVA

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

코드설명

구현(Implementation) 문제입니다.

 

문제를 이해하기 위해,

문제의 기본 접근은,

1. 홀수 노드끼리 연결

2. 짝수 노드끼리 연결

3. 홀수 첫번째 노드가 짝수 첫번쨰 노드를 가리키도록 연결

 

위 3가지를 구현하면 됩니다.

 

그 과정에서, 어떻게 1번, 2번 과정을 손쉽게 연결할 수 있는 것인가를 이해하기 위해서는,

첫번째 홀수, 짝수 노드가 하나의 그룹,

두번째 홀수, 짝수 노드가 하나의 그룹.

...

이렇게 연속된 2개가 하나의 그룹이라고 생각합니다.

그리고 이 그룹에서 뒤에 있는 짝수 노드를 기준으로 다음 그룹이 존재하는지, 존재하지 않는지를 체크하면서 이동한다면, 뒤에 그룹이 더 존재하는지 존재하지 않는지를 알 수 있습니다.

 

위의 조건을 구현한것이 아래입니다.

while(even != null && even.next != null){

even != null 일때는 마지막 그룹이 홀수로만 이루어져있을때,

even.next != null 일떄는 마지막 그룹이 홀수 짝수로 이루어져있고, 더이상 연결되어 있지 않을때를 의미합니다.

 

만약 두개 중 한개라도 null 이라면, 더 이상 연결할 수 없음을 의미하니, 멈추면 되겠습니다.

그림으로 보면, 

(1) -> (2) -> (3) 인 경우.

(1) -> (2) -> (3) -> (4) 인경우로 생각해보면 될 것 같습니다. 

더 이상 연결할 노드가 없지요.

 

코드

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode oddEvenList(ListNode head) {
        if(head == null || head.next == null) return head;
 
        ListNode odd = head;
        ListNode even = head.next;
        ListNode evenHead = even;
 
        while(even != null && even.next != null){
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
        }
 
        odd.next = evenHead;
        return head;
    }
}