[자바 알고리즘 인터뷰] 8장 연결 리스트(6) - 홀짝 연결 리스트

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

 

 

- 연결 리스트를 홀수 번째 노드 다음에 짝수 번째 노드가 오도록 재구성하라. 공간 복잡도 O(1), 시간복잡도 O(n)에 풀이하라 

 

 

풀이 1) 반복 구조로 홀짝 노드 처리 

 

- 홀수 노드 다음에 짝수 노드가 오게 재구성하라고 했으니 홀(Odd), 짝(Even) 각 노드를 구성한 다음 홀수 노드의 마지막을 짝수 노드의 처음과 이어 주면 될 것같다. 

 

- 홀수 노드 odd는 1에서 시작하고, 짝수 노드 even은 2에서 시작해 1->3->5, 2->4->6으로 이어지게 한 다음, 홀수 노드의 마지막인 5의 다음 노드를 짝수 노드의 처음인 2로 이어주면 된다. 

 

- 짝수 노드가 존재한다면 계속 반복하면서 홀수 노드는 홀수끼리, 짝수 노드는 짝수끼리 이어나가며 한 칸씩 진행

 //반복하면서 홀짝 노드 처리 
while(even != null && even.next!= null)
{
    //홀짝 노드의 다음 노드로 다음 다음 노드 진행 
    odd.next = odd.next.next;
    even.next = even.next.next;
    
    //홀짝 한칸씩 진행
    odd = odd.next;
    even = even.next;
}

 

- 끝까지 진행한 다음에 odd는 홀수 노드의 가장 마지막 노드이므로  그 다음 노드로 사전에 미리 선언해두었던 짝수 노드의 첫 번째 evenHead로 연결 

 

//홀수 노드 마지막을 짝수 첫 번째와 연결
odd.next = evenHead;

 

출처 : 자바 알고리즘 인터뷰 with 코틀린 저자: 박상길 <책만>

 

 

class Solution {
    public ListNode oddEvenList(ListNode head) {
        //예외 처리
        if(head == null)
            return null;
        
        //홀수 노드 
        ListNode odd = head;
        //짝수 노드
        ListNode even = head.next;
        //짝수 첫 번째 노드 
        ListNode evenHead = even;

        //반복하면서 홀짝 노드 처리 
        while(even != null && even.next!= null)
        {
            //홀짝 노드의 다음 노드로 다음 다음 노드 진행 
            odd.next = odd.next.next;
            even.next = even.next.next;
            //홀짝 한칸씩 진행
            odd = odd.next;
            even = even.next;
        }

        //홀수 노드 마지막을 짝수 첫 번째와 연결
        odd.next = evenHead;
        
        //첫번째 노드 리턴
        return head;
    }
}