328. Odd Even Linked List

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

Odd Even Linked List - LeetCode

 

홀수번째 연결리스트 뒤에 짝수번째 연결리스트가 오도록 재배열하는 문제이다.

 

---

 

1. 문제 이해

=> 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. (원본 배열을 수정하면 안됨.)

=> You must solve the problem in O(1) extra space complexity and O(n) time complexity. (새로운 연결리스트를 만드는 식의 접근은 불가.)

 

Constraints:

• n == number of nodes in the linked list
• 0 <= n <= 104
• -106 <= Node.val <= 106

n이 0, 1, 2인 경우도 고려해야 할듯.

 

---

2. 문제 재정의

 

문제에서 말한 사항 그대로. 고로 재정의는 스킵.

 

---

3. 계획 수립

 

1. 새로운 연결리스트를 만드는 방식 => 제한 사항에 걸림( O(n)의 메모리를 차지.)

2. 투포인터를 이용한 방식 => 홀수 번과 짝수 번 포인터를 만들어서, 홀수 번째는 홀수 번째끼리 연결시키고, 짝수 번째는 짝수 번째끼리 연결시킴. 그래서 맨 나중에 홀수번째 끝과 짝수번째 처음을 연결시키면 됨. 

 

 

 

---

4. 계획 검증 

 

n이 0, 1, 2일 시에는 연결 안해줘도 똑같기 때문에 그냥 헤드 노드를 리턴.

연결 리스트가 홀수 번째에 끝나는 경우, 짝수 번째에 끝나는 경우 모두 만족.

단, 짝수 번째의 마지막 노드는 nullptr을 가르킴으로써, 사이클을 방지.

 

 

 

---

 

5. 프로그램 구현 

 

 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        ListNode *odd = head;
        ListNode *even = head == nullptr? nullptr : head->next;
        ListNode *evenFirst = even;
        
        if (odd == nullptr || even == nullptr || even->next == nullptr) return head;
        
        while (odd->next != nullptr  && even->next != nullptr ) {

            if (odd->next == even) {
                odd->next = even->next;
                odd = even->next; 
            } else {
                even->next = odd->next;
                even = odd->next;
            }
        };
        
        even->next = nullptr;
        odd->next = evenFirst;
        
        return head;
    }
};

 

 

 

---

 

 

6. 피드백 & 복기

 

 

 

더 효율적인 코드

 

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        
        if(!head) return nullptr;
        
        ListNode *h1 = head;
        ListNode *h2 = head->next;
        ListNode *p1 = head;
        ListNode *p2 = head->next;
        

        while(p1 && p2 && p2->next) {
            p1->next = p2->next;
            if(p1->next != nullptr) {
                p1 = p1->next;
            }
            p2->next = p1->next;
            if(p2->next != nullptr) {
                p2 = p2->next;
            }
        }

        p1->next = h2;
        
        return h1;
    }
};

 

 

아래는 solution 코드.

 

public class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null) return null;
        ListNode odd = head, even = head.next, 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;
    }
}