Linked List | Odd Even Linked List

Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list. The first node is considered odd, and the second node is even, and so on. Note that the relative order inside both the even and odd groups should remain as it was in the input.

Linked List가 주어졌을 때, 홀수번째 노드들과 짝수번째 노드들을 나누어서, 모든 홀수는 앞쪽에, 모든 짝수는 뒷쪽에 두라는 문제이다. Leetcode에서 Medium 난이도의 문제이다. 또한, 아래와 같은 조건이 있다.

노드 갯수는 0부터 10,000개까지이고, 숫자는 -1,000,000 부터 1,000,000까지가 들어올 수 있다. 그러므로, linked list를 최소한으로 도는것도 중요하지만, Node안에 들어있는 값 또한 크기때문에, 노드의 값들을 따로 저장하는것 또한 주의해야한다. 그래서, 문제에서 조언해준대로, O(N)의 Time Complexity, 그리고 O(1)의 Space Complextity로 문제를 푸는 방법으로 접근했다.

class Solution {
    public ListNode oddEvenList(ListNode head) {
        if(head == null || head.next == null) return head;
        
        ListNode curr = head;
        ListNode oddHead = new ListNode(-1);
        ListNode oddCurr = oddHead; 
        ListNode evenHead = new ListNode(-1);
        ListNode evenCurr = evenHead;
        boolean oddTurn = true;
        while(curr != null){
            ListNode temp = curr;
            if(oddTurn){
                oddCurr.next = curr;
                oddCurr = oddCurr.next;
            } else {
                evenCurr.next = curr;
                evenCurr = evenCurr.next;
            }
            curr = curr.next;
            temp.next = null;
            oddTurn = !oddTurn;
        }
        oddCurr.next = evenHead.next;
        return oddHead.next;
    }
    
    private void printLinkedList (String name, ListNode node){
        System.out.print(name + ": [");
        while(node != null){
            System.out.print(node.val + ",");
            node = node.next;
        }
        System.out.println("]");
    }
}

* O(N)의 Time Complexity, O(1)의 Space Complextity

(아래 printLinkedList는 디버깅용으로 사용했던 function이다.)

 

odd와 even리스트를 따로 만들긴 하지만, 기존에 있었던 리스트를 사용하는 방법을 취했다. 여기서 세가지 방법을 사용했다. 첫번째로 지금이 홀수번째인지, 짝수번째인지를 알기 위해 oddTurn이라는 boolean을 생성해서 매 loop마다 바꾸어주었다. 두번째로는, temp를 이용해서 curr node를 저장해주고, 다음 loop을 위해서 curr 값을 다음으로 넘겨준 후, temp.next를 null로 바꿔주는것이다. 이렇게 해야 맨 마지막 노드가 다른 노드를 가르키는 버그를 피할 수 있다. 이 방식 말고도 loop이 끝난 후에, 확실하게 하기 위해 oddCurr.next 그리고 evenCurr.next를 null로 세팅해주는 방법도 있다. 마지막으로, odd, curr마다 포인터를 사용해서 dummy heads를 만들어주고, 새로운 노드값이 올때마다 각 리스트의 curr.next값으로 지정해준 후, curr 포인터를 한발짜국 옮기는것이다. 모든 loop이 끝난 후, oddCurr.next를 evenHead (dummy node)의 다음으로 연결해주면 정렬된 하나의 linkedlist가 된다. 이후, oddHead(dummy node)의 다음 노드를 리턴해주면 된다.

 

이 알고리즘으로 풀었을 때, 최상위(100%)의 속도와 최상위(92.53%)의 효율적인 메모리 사용을 보여주었다.

 

https://www.pinterest.at/pin/739364463797070476/

"위 포켓몬 그룹에서 피카츄를 시작으로 맨 앞부터 홀수번째 포켓몬은 앞쪽에, 짝수번째 포켓몬은 뒤쪽에 정렬해서 한줄로 리턴해라"

 

 

 

 

Reference

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

Odd Even Linked List - LeetCode