청정알고리즘

문제

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of kthen left-out nodes in the end should remain as it is.

풀이

list 문제의 연속이다.

전체 길이를 구한다음 k개씩 묶어서 각각을 뒤집는다. 뒤집는 과정은 다음과 같다.

Time Complexity : $O(n)$

코드

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if(head==NULL || k==1)return head;
        ListNode* prev = new ListNode(0);
        prev->next = head;
        
        int l=0;
        for(ListNode* it = head; it!=NULL; it=it->next)l++;
        
        ListNode *p = prev;
        for(int i=0;i+k<=l;i+=k)
        {
            ListNode* now = p->next;
            ListNode* nxt = now->next;
            for(int j=1;j<k;j++)
            {
                now->next= nxt->next;
                nxt->next =p->next;
                p->next = nxt;
                nxt =now->next;
            }
            p=now;
        }
        return prev->next;
    }
};

문제

Given a linked list, swap every two adjacent nodes and return its head.

You may not modify the values in the list's nodes, only nodes itself may be changed.

풀이

기본적인 list 구현문제이다.

적당한 list 연산을 이용해서, 위의 list를 아래와 같이 변형시켜주는 계산을 진행한다.

Time Complexity : $O(n)$

풀이

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* prev = new ListNode(0);
        prev->next=head;
        for(ListNode *it=prev; it!=NULL;)
        {
            if(it->next==NULL || it->next->next==NULL) break;
            ListNode *temp=it->next;
            it->next=it->next->next;
            temp->next = it->next->next;
            it->next->next=temp;
            it=temp;
        }
        return prev->next;
    }
};

문제

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

풀이

우리는 Merge Two Sorted Lists를 알고있다고 가정하자.

그렇다면 분할정복을 이용해서 문제를 해결할 수 있다.

list를 절반으로 나눠서 각각의 Merge k/2 Sorted Lists를 구한 다음, 이 두 list를 Merge Two Sorted Lists로 합치면 끝.

시간복잡도를 $T(list)$이라 한다면 $T(list)=T(l)+T(r)+O(|N|)$이므로 $T(list)=O(|N|logk)$이다.

(여기서 |N|은 총 노드의 수, k는 list의 원소의 수)

Time Complexity : $O(|N|logk)$

코드

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution{
private:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode * ans=new ListNode(0);
        ListNode * it =ans;
        for(ListNode* i1=l1, *i2=l2; i1 || i2;it=it->next)
        {
            if(i1==NULL)
            {
                it->next=i2;
                i2=i2->next;
            }
            else if(i2==NULL)
            {
                it->next=i1;
                i1=i1->next;
            }
            else if(i1->val>i2->val)
            {
                it->next=i2;
                i2=i2->next;
            }
            else
            {
                it->next=i1;
                i1=i1->next;
            }
        }
        return ans->next;
    }
    ListNode* merge(int l, int r, vector<ListNode*>& lists)
    {
        if(l==r) return NULL;
        if(l+1==r) return lists[l];
        int mid=(l+r)/2;
        return mergeTwoLists(merge(l,mid,lists), merge(mid,r,lists));
    }
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(0,lists.size(),lists);
    }
};