[C/LeetCode] Swapping Nodes in a Linked List

Daily LeetCoding Challenge April, Day 4

 

문제

linked list에서 앞에서 K번째, 뒤에서 k번째 요소를 swapping

 

아이디어: 직접 탐색 + linear 순회

먼저 linked list안에 몇개의 node가 있는지 확인해야 한다. 그래야 뒤에서 부터 몇번째는 몇번의 loop를 돌아야 하는지 계산 가능하기 때문.

총 n개의 node가 있다고 하면 (n-k+1) 번의 loop를 돌면 뒤에서부터 K번째 요소이다.

 이 둘의 값을 바꾸면 된다.

 

예외 사항

1. K == 0

2. head == NULL

하지만 문제에서 1<=k<=n<=10^5 라고 지정했으므로 위와 같은 예외사항은 처리하지 않아도 된다.

 

완성

submission: 333ms / 48.2MB

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* swapNodes(struct ListNode* head, int k){
    int len = 0, index = 1;
    int val1, val2;
    struct ListNode *temp;
    
    temp = head;
    while (temp != NULL)
    {
        len++;
        temp = temp->next;
    }
    
    temp = head;
    while (index++ < k)
        temp = temp->next;
    val1 = temp->val;
    
    temp = head;
    index = 1;
    while (index++ < len - k + 1)
        temp = temp->next;
    val2 = temp->val;
    temp->val = val1;
    
    temp = head;
    index = 1;
    while (index++ < k)
        temp = temp->next;
    temp->val = val2;
    
    return head;
}

 

생각해보니 순회는 한번씩만 돌아도 되겠다고 생각했다.

 

완성2

submission: 494ms / 48.5

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

void swapping(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
struct ListNode* swapNodes(struct ListNode* head, int k){
    int len = 0;
    struct ListNode *start;
    struct ListNode *end;
    
    start = head;
    while (start != NULL)
    {
        len++;
        start = start->next;
    }
    
    start = head;
    for(int i = 1;i < k;i++)
        start = start->next;
    
    end = head;
    for(int i = 1;i < len - k + 1;i++)
        end = end->next;
    
    swapping(&start->val, &end->val);
    return head;
}

 

코드는 클린해졌는데 왜 실행 시간이랑 메모리는 늘어날까? 당연함 외부 함수가 있어서임