LeetCode 328. Odd Even Linked List 자바 문제 풀이

문제

Odd Even Linked List - LeetCode

문제 해결 방법

• 링크드리스트를 잘 다룰수 있는지 묻는 문제입니다.
• 첫번쨰 노드가 null일떄, 두번쨰 노드가null일떄, 세번쨰 노드가 null일떄는 그대로 반환합니다.
  • null → 그대로 리턴
  • 1-null → 그대로 리턴
  • 1-2-null → 그대로 리턴
  • 1-2-3-null → 1-3-2로 리턴이 필요함
• odd와 even 링크드리스트를 따로따로 만들고, 나중에 odd마지막에 even을 연결하는 알고리즘이면 풀수 있습니다.
• 위의 연결과 리턴값을 위해 각각 oddHead와 evenHead를 따로 선언해놓아야 합니다.
• 두번씩 연결하기 떄문에 루프문의 조건을 head ! =null 이 아니라 head.next까지 널체크 해야합니다.

Github Link

https://github.com/eunhanlee/LeetCode_328_OddEvenLinkedList_Solution.git

시간복잡도: O(n), 공간복잡도: O(1)

public class Solution {

    /**
     * 연결 리스트에서 홀수 인덱스 노드가 짝수 인덱스 노드보다 앞에 오도록 재배열합니다.
     *
     * @param head 연결 리스트의 헤드 노드
     * @return 재배열된 연결 리스트의 헤드 노드
     */
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return head;
        }

        ListNode oddHead = head;
        ListNode evenHead = head.next;
        ListNode odd = oddHead;
        ListNode even = evenHead;

        // 홀수 노드와 짝수 노드를 따로 연결하도록 리스트를 반복적으로 탐색합니다.
        while (even != null && even.next != null) {
            odd.next = even.next; // 현재 홀수 노드를 다음 홀수 노드에 연결합니다.
            odd = odd.next; // 다음 홀수 노드로 이동합니다.
            even.next = odd.next; // 현재 짝수 노드를 다음 짝수 노드에 연결합니다.
            even = even.next; // 다음 짝수 노드로 이동합니다.
        }

        odd.next = evenHead; // 홀수 노드의 꼬리를 짝수 노드의 헤드에 연결합니다.
        return oddHead; // 재배열된 리스트의 헤드 노드를 반환합니다.
    }
}

설명