[LeetCode] 1721. Swapping Nodes in a Linked List

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

Swapping Nodes in a Linked List - LeetCode

문제 유형 : 연결 리스트

문제 난이도 : Medium

 

문제

You are given the head of a linked list, and an integer k.

Return the head of the linked list after swapping the values of the kth node from the beginning and the kth node from the end (the list is 1-indexed).

 

연결리스트와 정수 k를 받는다. 시작에서 k번째 노드와 끝에서 k번째 노드의 위치를 바꿔라.

 

 

풀이

node1은 쉽게 구할 수 있다. node2를 한 번의 순회로 구하는 법은 node1에 runner라는 포인터를 만들어준 뒤, node2는 첫 노드에 초기화해준다. runner를 끝까지 보내면서 node2도 다음으로 이동시키면 node2는 뒤에서 k번째인 노드에 도착한다.runner와 node2의 거리는 항상 k임을 이용한 것이다.

 

그 뒤, 두 노드를 바꿔주면 된다.

 

코드(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) {
        if (head == nullptr)
            return nullptr;

        ListNode* node1 = nullptr;
        ListNode* prev_node1 = nullptr;
        ListNode* node2 = nullptr;
        ListNode* prev_node2 = nullptr;
        ListNode* current = head;
        int count = 0;

        // Find the kth node from the beginning
        while (current != nullptr) {
            count++;
            if (count == k) {
                node1 = current;
                break;
            }
            prev_node1 = current;
            current = current->next;
        }

        ListNode* runner = node1;
        while (runner != nullptr) {
            prev_node2 = node2;
            node2 = (node2 == nullptr) ? head : node2->next;
            runner = runner->next;
        }

        if (node1 == nullptr || node2 == nullptr){
            return head;
        }

        if (prev_node1 != nullptr)
            prev_node1->next = node2;
        else
            head = node2;

        if (prev_node2 != nullptr)
            prev_node2->next = node1;
        else
            head = node1;

        ListNode* temp = node1->next;
        node1->next = node2->next;
        node2->next = temp;

        return head;
    }
};