[Leetcode] 1721. Swapping Nodes in a Linked List 문제 풀이

https://leetcode.com/problems/swapping-nodes-in-a-linked-list/

Swapping Nodes in a Linked List - LeetCode

문제 내용

index 0(왼쪽)부터 시작했을 때 k번째 node와

index size-1 (오른쪽)부터 시작했을 때 k번째 node를

swap하는 문제

 

Example 1:

Input: head = [1,2,3,4,5], k = 2
Output: [1,4,3,2,5]

Example 2:

Input: head = [7,9,6,6,7,8,3,0,9,5], k = 5
Output: [7,9,6,6,8,7,3,0,9,5]

 

문제 풀이

index가 0인 왼쪽부터 시작했을 때 k번째는 단순하게 반복문만 돌아도 구할 수 있다.

문제는 오른쪽에서 시작했을 때 k번째를 찾는 부분이다.

역순으로 하는 방법중에 재귀를 이용하는 방법이 있다.

재귀는 stack 구조로 들어갔다가 하나씩 거꾸로 나와서 이 부분을 활용했다.

 

코드

C++

/**
 * 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* swapNodes(ListNode* head, int k) {
        auto s = getBeginningNode(head, k);
        auto e = getEndNode(head, k);
        swap(s->val, e->val);
        return head;
    }
    ListNode* getBeginningNode(ListNode* head, int k) {
        for (int i = 1; i < k; ++i) {
            head = head->next;
        }
        return head;
    }
    ListNode* getEndNode(ListNode* head, int& k) {
        if (head == nullptr)
            return nullptr;
        
        auto node = getEndNode(head->next, k);
        if (k == 0) {
            return node;
        }   
        else{
            k--;
            return head;
        }
    }
};

Kotlin

/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun swapNodes(head: ListNode?, k: Int): ListNode? {
        var beginningNode = head?.let { 
            var node = it
            repeat(k-1) {
                node = node?.next
            }
            node
        }
        var endNode = head?.let {
            var node = it
            var size = 1
            while(true) {
                if (node?.next == null)
                    break
                node = node?.next
                size++
            }
            node = it
            repeat(size-k) {
                node = node?.next
            }
            node
        }
        beginningNode?.`val` = endNode?.`val`.also { endNode?.`val` = beginningNode?.`val` }
        return head
    }
}

코틀린할 때 while (node != null) 이 안되서 while (true)로 했다.

while (node != null) 로 하면 조건문에 의해 ListNode? -> ListNode로 변하면서 null체크가 안되고 must not be null error가 발생했다.