93일 (1721. Swapping Nodes in a Linked List) pointers

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).

 

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]

 

Constraints:

• The number of nodes in the list is n.
• 1 <= k <= n <= 10^5
• 0 <= Node.val <= 100

 

- 접근방법

 

주어지는 ListNode는 연결리스트를 객체로 구현한 것이다.

ListNode는 현재노드와 그 다음 노드만을 기억하므로 ListNode의 총 길이는 직접 순회하지 않는 이상 알 수 없다.

 

1. 처음부터 끝까지 ListNode를 순회하는 currentNode가 필요하다.

2. 현재 몇 번째 노드인지 기억하는 변수 cnt가 필요하다.

3. K번째 ListNode의 값을 가르키는 ListNode node1이 필요하다.

4. (ListNode의 총 길이 - K번째)의 값을 가르키는 ListNode node2가 필요하다.

5. node1과 node2의 value를 스왑해준다.

6. head를 리턴한다.

 

 

 

- 코드 (pointers)

 

class Solution {
    public ListNode swapNodes(ListNode head, int k) {
        int cnt = 1;
        ListNode node1 = null;
        ListNode node2 = head;
        ListNode currentNode = head;

        while (currentNode != null) {
            if (cnt == k) node1 = currentNode; // 3.
            if (cnt - k > 0) node2 = node2.next; // 4.

            currentNode = currentNode.next;
            cnt++; // 총 길이
        }

        int temp = node1.val; // k번째, 전체-k번째 value 스왑
        node1.val = node2.val;
        node2.val = temp;

        return head;
    }

    private class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

}

 

 

특출난 코드는 아니지만 정석적인 방법이라고 생각은 한다.

전체길이를 모르기 때문에 while문의 끝에 도달할 때까지 (현재위치-k)번째 노드를 기억하는게 중요하였다.

 

 

 

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

Swapping Nodes in a Linked List - LeetCode