LeetCode 86. Partition List

🗓️ Daily LeetCoding Challenge August, Day 15

Linked List

Linked List 문제는 처음 풀어본다. 간접적으로 array을 이용해서 비슷하게는 풀어봤지만, linked list 자체를 사용해본건 이번이 처음. 문제에서 떡하니 ListNode가 정의되어 있어서 많이 당황했다. 어떻게 값을 불러오는지조차 망설이게 되었다. 예제를 이용해서 실제 linked list을 그리면서 풀어보니까 이해가 잘 되었다.

나의 풀이

Linked List는 목걸이처럼 각 Node가 꼬리에 꼬리를 무는 형태의 자료구조이다. array와는 다르게 index가 정해지지 않고 각 Node는 val 데이터 필드와 다음 Node를 가리키는 *next 링크 필드를 가진다. 비엔나소시지처럼 줄줄이 엮어내면 linked list가 완성된다. index 고려를 크게 하지 않아도 돼서 비교적 간단하게 풀어낼 수 있다.

/**
 * 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* partition(ListNode* head, int x) {
        // head->1->4->3->2->5->2

        ListNode* curr = head;
        ListNode* less_head = new ListNode(0); // dummy node (node < x)
        ListNode* less_tail = less_head; // less tail pointer
        ListNode* large_head = new ListNode(0); // dummy node (node >= x)
        ListNode* large_tail = large_head; // large tail pointer

        while (curr != nullptr){
            if (curr -> val < x){
                less_tail -> next = new ListNode(curr -> val);
                less_tail = less_tail -> next; // move tail pointer
            } else{
                large_tail -> next = new ListNode(curr -> val);
                large_tail = large_tail -> next; // move tail pointer
            }
            curr = curr -> next; // to the next node
        }

        // result
        // less_head->0->1->2->2
        // large_head->0->4->3->5

        less_tail -> next = large_head -> next;
        // concatenate less and large List
        // less_head->0->1->2->2->4->3->5        

        return less_head -> next;
        // 1->2->2->4->3->5
    }
};