[C++] ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ(Linked List)

2022. 9. 27. 20:19ยท๐Ÿ“ Computer Science/โœ Algorithm

์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ(Linked List)

 

๋ฌธ์ œ

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

 

Add Two Numbers - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

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

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

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

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

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

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

#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

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

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

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

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;
    }
};
์ €์ž‘์žํ‘œ์‹œ (์ƒˆ์ฐฝ์—ด๋ฆผ)
'๐Ÿ“ Computer Science/โœ Algorithm' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
  • [C++] ํŽธ์ง‘ ๊ฑฐ๋ฆฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜(Edit Distance Algorithm)
  • ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ •๋ฆฌ
  • [C++] ํ‰ํ–‰ ๋ถ„ํ• , ๋ชจ์Šค ์•Œ๊ณ ๋ฆฌ์ฆ˜
  • [C++] ๋ˆ„์  ํ•ฉ(Prefix sum)
Blxxming
Blxxming
CS ์ง€์‹๊ณผ ๊ณต๋ถ€ํ•˜๋‹ค ๋ฐฐ์šด ๊ฒƒ, ๊ฒฝํ—˜ํ•œ ๊ฒƒ ๋“ฑ์„ ๊ธฐ๋กํ•˜๋Š” ๋ธ”๋กœ๊ทธ์ž…๋‹ˆ๋‹ค.
  • Blxxming
    ๐Ÿ’ก๋ฒˆ๋œฉ๐Ÿ’ก
    Blxxming
  • ์ „์ฒด
    ์˜ค๋Š˜
    ์–ด์ œ
  • ๊ณต์ง€์‚ฌํ•ญ

    • Tech Interview
    • ๐Ÿ“š Tech (246)
      • ๐Ÿ“ Computer Science (96)
        • โœ OS (12)
        • โœ Network & Web (10)
        • โœ Database (11)
        • โœ Data Structure (6)
        • โœ Algorithm (40)
        • โœ Design Pattern (9)
        • โœ Cloud Computing (3)
        • โœ (5)
      • ๐Ÿ“ Language (73)
        • โœ Language (6)
        • โœ C & C++ (11)
        • โœ C# (19)
        • โœ JAVA (37)
      • ๐Ÿ“ Game (43)
        • โœ Computer Graphics (2)
        • โœ Unity (14)
        • โœ Unreal (26)
        • โœ (1)
      • ๐Ÿ“ Book (34)
        • โœ Effective (3)
        • โœ Game Server (16)
        • โœ Clean Code (14)
        • โœ (1)
  • hELLOยท Designed By์ •์ƒ์šฐ.v4.10.0
Blxxming
[C++] ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ(Linked List)
์ƒ๋‹จ์œผ๋กœ

ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”