[C++] 연결 리스트(Linked List)

연결 리스트(Linked List)

 

문제

https://leetcode.com/problems/add-two-numbers/

Add Two Numbers - LeetCode

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* root = new ListNode();
        ListNode* node = root;
        int num = 0;

        while (true) {
            if (l1) {
                num += l1->val;
                l1 = l1->next;
            }
            if (l2) {
                num += l2->val;
                l2 = l2->next;
            }

            node->val = num % 10;
            num /= 10;

            if (l1 || l2 || num) {
                node->next = new ListNode();
                node = node->next;
            }
            else
                break;
        }

        return root;
    }
};

 

https://leetcode.com/problems/remove-nth-node-from-end-of-list/

Remove Nth Node From End of List - LeetCode

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if (head->next == nullptr)
            return nullptr;

        ListNode* temp = head;
        int size = 0;
        while (temp != nullptr) {
            size++;
            temp = temp->next;
        }

        ListNode* node = head;
        ListNode* pre = head;
        for (int i = 0; i < size; ++i) {
            if (i == size - n) {
                if (node == head) // 시작
                    head = head->next;
                else if (node->next == nullptr) // 끝
                    pre->next = nullptr;
                else
                    pre->next = node->next;

                delete(node);
                break;
            }

            pre = node;
            node = node->next;
        }

        return head;
    }
};

 

https://leetcode.com/problems/merge-two-sorted-lists/

Merge Two Sorted Lists - LeetCode

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 *mergeTwoLists(ListNode *list1, ListNode *list2)
    {
        if (list1 == nullptr)
            return list2;
        if (list2 == nullptr)
            return list1;
        if (list1->val < list2->val)
        {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        }
        else
        {
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        }
    }
};

 

https://leetcode.com/problems/merge-k-sorted-lists/

Merge k Sorted Lists - LeetCode

#include <vector>
using namespace std;

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 *mergeKLists(vector<ListNode *> &lists)
    {
        if (lists.size() == 0)
            return nullptr;

        ListNode *answer = lists[0];
        for (int i = 1; i < lists.size(); ++i)
            answer = mergeTwoLists(answer, lists[i]);
        return answer;
    }

    ListNode *mergeTwoLists(ListNode *list1, ListNode *list2)
    {
        if (list1 == nullptr)
            return list2;
        if (list2 == nullptr)
            return list1;
        if (list1->val < list2->val)
        {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        }
        else
        {
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        }
    }
};

 

https://leetcode.com/problems/swap-nodes-in-pairs/

Swap Nodes in Pairs - LeetCode

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 *swapPairs(ListNode *head)
    {
        ListNode *node = head;
        ListNode *preNode = node;
        int preVal = -1;
        while (node != nullptr)
        {
            if (preVal == -1)
            {
                preNode = node;
                preVal = node->val;
            }
            else
            {
                preNode->val = node->val;
                node->val = preVal;
                preVal = -1;
            }
            node = node->next;
        }
        return head;
    }
};

 

https://leetcode.com/problems/reverse-nodes-in-k-group/

Reverse Nodes in k-Group - LeetCode

class Solution
{
public:
    ListNode *reverseKGroup(ListNode *head, int k)
    {
        ListNode *root = head;
        vector<ListNode*> v(k);

        while (true)
        {
            for (int i = 0; i < k; ++i)
            {
                if (root == nullptr)
                    return head;
                v[i] = root;
                root = root->next;
            }

            for (int i = 0; i < k / 2; i++)
                SwapVal(v[i], v[k - i - 1]);
        }
    }

    void SwapVal(ListNode *node1, ListNode *node2)
    {
        int val = node1->val;
        node1->val = node2->val;
        node2->val = val;
    }
};