[Java] LeetCode 1721. Swapping Nodes in a Linked List

[Java] LeetCode 1721. Swapping Nodes in a Linked List

 

문   제 : 

List와 정수 k가 주어진다. 

List 에서 앞에서 k번째의 노드와 뒤에서 k번째의 노드의 값을 바꾼 List를 반환해라.

 

Constraint

{ 1 <= k <= n <= 10^5 }

{ 0 <= Node.val <= 100 }

 

Matter

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 )

Input: head = [1,2,3,4,5], k = 2
Output: [1,4,3,2,5]

=========================================================================

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]

 

 

---

접   근 : 

List의 전체 크기를 구해서 앞에서부터 k번째 노드의 값을 구하고, 전체 사이즈-k번째의 값을 구한다.

---

해    결  &  설    명: 

List를 처음부터 끝까지 순회하면서 k번째 노드의 값을 구한다. 만약, k번째가 전체 사이즈일 때를 고려해, while문이 끝나고 한번 더 체크해준다.

 

다시 List를 처음부터 순회하는데, 이번에는 size-k번째의 노드의 값을 구한다. (뒤에서 k번째 노드) 

 

두 노드의 값을 바꿔준다.

 

---

결   과  :

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapNodes(ListNode head, int k) {
        // 앞에서 k번째 노드랑 뒤에서 k번째 노드랑 자리 바꾸기
        ListNode cur, fromStart, fromEnd;
        int size = 1;
        int temp;

        fromStart = head;
        cur = head;

        while(cur.next != null) {
            if(size == k) fromStart = cur;
            size++;
            cur = cur.next;
        }
        if(size == k) fromStart = cur;

        fromEnd = head;
        for(int i=0; i<size-k; i++){
            if(fromEnd.next != null)
                fromEnd = fromEnd.next;
        }

        temp = fromStart.val;
        fromStart.val = fromEnd.val;
        fromEnd.val = temp;

        return head;
    }
}