[Leetcode] 1721. Swapping Nodes in a Linked List

오늘은 Linked List 내의 특정 노드들을 swap 하는 문제를 풀어보겠다.

March Leetcode Challenge 2021 에서 3월 14일 (PST) 에 출시된 문제이다.

 

문제는 아래 링크를 참고하시면 된다.

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

Swapping Nodes in a Linked List - LeetCode

 

문제를 읽어보면 입력으로 Linked List 와 k 가 주어지는데, k 는 Linked List 의 사이즈보다 클 수 없다.

노드의 값은 100 이하라는 조건의 경우에는, 딱히 신경쓰지 않아도 될 것 같다. (혹시 신경써야 할 이유가 있으시면 댓글 바랍니다.)

 

시작부터 k 번째의 노드와 끝에서부터 k 번째의 노드를 바꾸라는 것이 요구사항이다.

시작인덱스는 1이라는 것도 명시되어 있는데, 이것도 유의해서 봐준다.

 

필자는 Two pointers 형태 (실제로는 Three) 로 One pass에 풀었다. 

 

전체코드를 복사&붙여넣기 하는 행위는 실력에 전혀 도움되지 않음을 명심하시길 바란다.

class Solution {
    public ListNode swapNodes(ListNode head, int k) {
        // 엣지케이스
        if (head == null) return new ListNode();
        /* Leetcode 가 아니라면 k가 입력된 head의 길이보다 작다는 것도 체크해줘야 함 */
        
        ListNode curr = head; // 탐색을 위한 노드
        ListNode first = head; // first 노드 (앞에서부터 k번째 노드)
        ListNode second = head; // second 노드 (뒤에서부터 k번째 노드)

        // k번째 노드를 찾기 위한 반복
        for (int i = 1; i < k; i++) { // 1인덱스임이 조건에 나와 있었음
            curr = curr.next; // 현재 노드에 다음 노드를 넣으면서 한 칸씩 전진
        }
        first = curr; // k번째 노드의 참조값을 first 노드에 저장
        
        // k번째 노드부터 입력된 head의 끝까지 탐색
        while (curr.next != null) {
            curr = curr.next; // 끝까지 탐색하기 위한 기준 노드
            second = second.next; // (총길이 - k)번째 노드를 찾기 위해 처음부터 출발
        }
        
        // second 노드를 찾았으니 first 노드의 값과 변경해줌
        int tmp = first.val;
        first.val = second.val;
        second.val = tmp;
        
        return head;
    }
}

---

인터뷰 상황에서 문제를 받으면 문제를 이해하고 설계부터 해야한다. 

(단순히 Leetcode 문제만 푼다면 해당 내용은 무시하고 주어진 템플릿을 활용하시면 된다.)

이 문제는 정수형 숫자를 가진 노드가 순서대로 연결되어 있으니 아래와 같은 Linked List 구조를 띄면 될 것이다.

Data

Reference

Linked List 는 위와 같이 하나의 노드에 데이터와 다음 노드의 참조값으로 이루어져 있다. 

public class ListNode {
    int val; // 정수
    ListNode next; // 다음 노드
    
    ListNode() {} // 기본 생성자
    ListNode(int val) { this.val = val; } // 생성자1
    ListNode(int val, ListNode next) { this.val = val; this.next = next; } // 생성자2
}

Leetcode 에서 제공하는 템플릿이 무난하니 그대로 가져다 쓴다.

---

앞에서 k번째 노드를 찾는 것은 크게 어렵지 않다. 뒤에서 k번째를 어떻게 찾아나갈 것인지에 대한 고민이 필요하다.

필자는 이 문제를 어디선가 본 적이 있어서 찾는 방법을 그냥 기억해버렸다. 외웠다기보다 몇번 마주치다보니... 자연스레...

총 길이가 5인 Linked List 가 주어지고 k가 2인 경우에, 2번 노드와 4번 노드의 값만 변경해주면 된다.

Linked List 문제에서 자주 등장하는 노드 자체를 스왑하는 형태는 다른 문제에 양보하기로 하자...

1

2

3

4

5

1

4

3

2

5

1 (실제로는 인덱스의 시작) 부터 k 까지 이동해서 도착하는 노드를 기억한다. 그 노드를 first 노드라고 지칭한다.

그리고 first 노드부터 입력 리스트의 마지막 노드까지 이동하면서, 처음부터 새로 출발하는 second 노드가 있다면, 둘 간의 간격은 k 가 된다. first 노드가 마지막 노드에 도착하면 second 노드의 위치는 (총길이 - k) 가 된다. 우리가 구하고자 하는 2개의 노드가 특정된 것이다. 두 개 노드의 값들을 변경해주면 될 것이다.

 

아래 그림들을 통해 확인해보자.

head의 1번 인덱스에 curr, first, second 들을 위치시킨다. (문제에서 주어진 1 인덱스)

curr는 처음부터 끝까지 탐색을 위해 노드이다. (k 번째에서 쉬었다가 끝까지 가는 One-pass 탐색)

first는 k번째의 노드를 저장하기 위한 노드이다.

second는 (총길이 - k) 번째 노드를 저장하기 위한 노드이다.

        ListNode curr = head; // 탐색을 위한 노드
        ListNode first = head; // 1번 노드 (앞에서부터 k번째 노드)
        ListNode second = head; // 2번 노드 (뒤에서부터 k번째 노드)

        // k번째 노드를 찾기 위한 반복
        for (int i = 1; i < k; i++) { // 1인덱스임이 조건에 나와 있었음
            curr = curr.next; // 현재 노드에 다음 노드를 넣으면서 한 칸씩 전진
        }
        first = curr; // k번째 노드의 참조값을 first 노드에 저장

위 코드와 사진처럼 처음부터 k까지 반복하다가 k에 도착하면, 해당 노드 (curr) 를 first 노드에 넣어준다. (Object 이므로 참조값이 복사됨)

 

앞에서 k 번째 노드를 찾았으니 뒤에서 k 번째 노드를 찾으러 갈 차례이다.

curr 노드와 first 노드의 위치는 동일하고 second 노드의 위치는 처음인 상황에서, curr 노드와 second 노드의 간격을 확인해보면 k 이다. 예시 그림에서는 k - 1 인데, 문제에서 주어진 1 인덱스 때문임을 기억해야 한다.

        // k번째 노드부터 입력된 head의 끝까지 탐색
        while (curr.next != null) {
            curr = curr.next; // 끝까지 탐색하기 위한 기준 노드
            second = second.next; // (총길이 - k)번째 노드를 찾기 위해 처음부터 출발
        }

while 내의 연산이 1번 수행 후에는 아래 그림과 같이 변경된다.

2번 수행 후에는 아래와 같이 변경된다.

3번 수행 후, curr.next 가 null 이므로 입력 head의 끝에 도착했다는 것을 알 수 있다.

second 노드가 위치한 노드가 뒤에서 k 번째 노드임을 알 수 있다.

우리가 필요로하는 앞에서 k 번째 노드와 뒤에서 k 번째 노드를 모두 찾았으니 아래 코드처럼 두 노드의 값만 변경해준다.

        // second 노드를 찾았으니 first 노드의 값과 변경해줌
        int tmp = first.val;
        first.val = second.val;
        second.val = tmp;

참조를 통해 값만 변경했으니 우리는 기존 입력 (head) 을 리턴해주면 값만 변경된 것을 확인할 수 있다.

---

3개의 포인터를 써서 1번 탐색했기 때문에 시간복잡도는 $O(n)$ 이고, 공간복잡도는 $O(1)$ 이 된다.

이중이 아닌 for/while 반복이 몇 개가 선형으로 된다면, 어차피 O(n) 이기 때문에 이 문제는 대부분 O(n) 에 수렴한다.

공간복잡도의 경우에도 Queue, Stack, Array 등이 사용될 문제는 아니라서 O(1) 이 될테니 복잡도 때문에 고민할 부분은 아니라고 생각된다.