Linked List | Swapping Nodes in a Linked List

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번째 노드의 값을 swap, 즉 바꾸라는 Medium 난이도의 문제이다. 아래와 같은 조건도 주었다.

노드의 값이 크지 않기때문에 swap하는것은 별로 큰 문제가 없겠지만, 총 리스트의 크기가 100,000 이기때문에 (컴퓨터에게는 그렇게 큰 숫자는 아니지만) 리스트를 travel 하는 숫자를 적게 하는것을 중점을 두고 풀었다. 첫번째로 접근한 방식은 아래와 같다.

class Solution {
    public ListNode swapNodes(ListNode head, int k) {
        int length = countLength(head);
        ListNode left = getKthNode(head, k);
        ListNode right = getKthNode(head, length - k + 1);
        swapValue(left, right);
        return head;
    }
    
    private int countLength(ListNode head){
        ListNode slow = head;
        ListNode fast = head;
        int length = 0;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next == null ? fast.next : fast.next.next;
            length++;
        }
        return fast == null ? length * 2 : length * 2 + 1;
    }
    
    private ListNode getKthNode(ListNode node, int k){
        for(int i = 1; i < k; i++){
            node = node.next;
        }
        return node;
    }
    
    private void swapValue(ListNode n1, ListNode n2){
        int temp = n1.val;
        n1.val = n2.val;
        n2.val = temp;
    }
    
    private ListNode getMid
}

* Time Complexity: O(N), 실제로는 왼쪽 오른쪽 노드가 총 N - 1회 움직이고, 길이를 재는것은 N/2회 걸린다.

* Space Complexity: O(1), 노드포인터만 사용했다.

 

리스트가 총 몇개의 노드인지 숫자를 세어서 저장해두고, 왼쪽 노드를 k번째 노드까지, 오른쪽 노드를 총길이 - k + 1 번째 노드까지 움직여준 후, 값을 swap하는 식으로 처리했다. swap을 하는것은 다른 Linked List관련된 function에서 사용될 수 있고, getKthNode도 2회 사용되었고, 다른곳에서도 사용할만한 함수여서 helper method로 처리했다. 길이를 잴 때, 시간 절감을 위해서, slow, fast 노드를 사용했고, fast 노드의 위치에 따라 길이가 odd인지 even인지를 판단해서 총 길이를 계산했다. Big O 로는 똑같은 O(N)이지만, 그것보다 반절의 시간을 절감했다. 하지만, 속도가 그렇게 빠르지는 않았다. O(N)으로 풀 수 있는 방식이 없는지 조금더 생각해보았다.

 

slow와 fast노드를 사용하되, 조금은 다른 방식으로 사용하는방법을 시도했다. 이렇게 하면, 총 정확히 N회만에 답을 얻을 수 있다.

class Solution {
    public ListNode swapNodes(ListNode head, int k) {
        ListNode first = getKthNode(head, k);
        ListNode slow = head;
        ListNode fast = first;
        while(fast.next != null){
            slow = slow.next;
            fast = fast.next;
        }
        swapValue(first, slow);
        return head;
    }
    
    private ListNode getKthNode(ListNode node, int k){
        for(int i = 1; i < k; i++){
            node = node.next;
        }
        return node;
    }
    
    private void swapValue(ListNode n1, ListNode n2){
        int temp = n1.val;
        n1.val = n2.val;
        n2.val = temp;
    }
}

* Time Complexity: O(N), 정확하게는 N-1 첫번째 노드부터 마지막노드까지 loop을 돈다.

* Space Complexity: O(1), 노드 포인터만 몇개 쓰였고, swap할 때 임시 int 저장소가 쓰였다.

 

먼저 앞에서 k번째 노드를 찾은 후, 그 노드를 저장해두고, 또 포인터를 또 하나 만들어서 하나는 head에서, 다른 하나는  k번째 노드에서 출발해서, 앞서가있는 노드가 맨 마지막 노드를 만나면, 뒤에 있는 노드는 자연스럽게 마지막 노드로부터 k번째 노드가 된다. getKthNode나 swapValue같은 함수는 유용하게 쓰일 것 같아서 그대로 두었고, 결과적으로 최상위 속도를 얻었다.

 

2014 동대문디자인플라자(DDP) ‘피카츄 쇼타임’ 행사 

앞에서 N번째 있는 피카츄의 머리띠를 뒤에서 두번째 있는 피카츄의 머리에 주려면? 일단 머리에 꽃을단 피카츄를 찾는다. 그 후 꽃을단 피카츄가 나 여깄어! 하고 말하면, 맨 앞줄의 피카츄는 뒤에 있는 피카츄가 "니가 2번이야" 하고 말해주고, 머리의 꽃을 단 피카츄가 동시에 뒷사람에게 "니가 1번이야" 하고 말해주고, 그것을 계속 하다가 맨 뒤에 있는 피카츄가 "니가 1번이야" 라는 소리를 듣는 시점이 오면, "니가 2번이야" 라는 소리를 들은 피카츄가 바로 뒤에서 N번째 있는 피카츄이다. 그러면 머리에 꽃을 단 피카츄는 전기 충격을 이용해서 그 피카츄에서 머리띠를 전송해주면 된다 킄ㅋ

 

 

Reference 

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

Swapping Nodes in a Linked List - LeetCode