.leetcode(328. Odd Even Linked List)

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

 

2. 2022/05/02 시도

소요시간: 15분

class Solution {
    public ListNode oddEvenList(ListNode head) {
        // find last odd node
        int counter = 1;
        ListNode lastOddNode = null;
        ListNode current = head;
        while (current != null) {
            if (counter % 2 == 1) {
                lastOddNode = current;
            }
            current = current.next;
            counter++;
        }
        
        // move even node
        counter = 1;
        ListNode prev = null;
        ListNode targetNode = lastOddNode;
        current = head;
        while (current != lastOddNode) {
            ListNode temp = current.next;
            if (counter % 2 == 0) {
                prev.next = temp;
                current.next = targetNode.next;
                targetNode.next = current;
                targetNode = targetNode.next;
            } else {
                prev = current;
            }

            current = temp;
            counter++;
        }
        
        return head;
    }
}

풀이 접근 과정

먼저 제일 오른쪽 홀수 노드를 찾는다.

그다음에 짝수번째 노드를 찾아서 제일 오른쪽 홀수 노드에 붙여준다.
제일 오른쪽 노드에 도달하면 멈춘다.

 

느낀점

• 두번째while문의 종료조건을 관성적으로 코딩하다보니(while (current != null)) 조금 헤맸다.
• https://silvergoni.tistory.com/entry/leetcode-206-Reverse-Linked-List를 기억하고 풀면 좋다. 여기서 노드를 어떻게 옮기는지에 대한 아이디어를 배울 수 있다.
• 노드 2개를 분리해서 합해주는 방식으로도 개발이 가능하다.

---

 

1. 2022.01.17 시도

소요시간: 31분(5분 구상, 26분 코딩)

class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null) {
            return null;
        }

        ListNode oNode = head;
        ListNode eNode = head.next;
        ListNode temp = head.next;
        while(eNode != null && eNode.next != null) {
            ListNode nextO = eNode.next;
            ListNode nextE = nextO.next;
            
            oNode.next = nextO;
            eNode.next = nextE;
            nextO.next = temp;
            
            oNode = nextO;
            eNode = nextE;
        } 
        
        return head;
    }
}

풀이 접근 과정

홀수번째는 앞으로보내고 짝수번째는 뒤로 보내서 몰아주는 문제였다.
홀수번째의 다음 것과 짝수번재의 다음 것을 미리 담아두어야겠다는 생각이 들어 nextO, nextE 변수를 만들었다.

홀수번쨰끼리 먼저 이어주고, 짝수번째끼리 이어주고, 그다음 홀수번째의 마지막과 기억해둔 짝수번째의 첫번재를 이어준다.

 

느낀점

• 첫번째로 기억할건 짝수번째의 첫번째를 빼두는 것이다. 그래야 홀수번째를 이어준다음 짝수번째의 첫번째와 연결이 가능하다.
• 문제 푸는 내내 순서가 너무 헷갈렸다. 변수명도 헷가리는데 한 몫했을까?라는 생각도 들었다. while조건을 구하는게 제일 까다로웠다.  전체 노드 갯수가 짝수개면 한번 더 안돌고 끝내도 되지만 홀수개면 한번 더 돌아야하는데 그 조건체크가 좀 혼란스러우면서 시간이 많이 늦춰졌다. 아쉽다.

 

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형