Swap Nodes in Pairs - LeetCode

Problem

1. input: 연결 리스트의 첫 노드 head

2. output: 주어진 연결 리스트를 두개씩 순서를 바꾼 후 리턴

   

• The number of nodes in the list is in the range [0, 100].
• 0 <= Node.val <= 100

Idea

커서를 통해 연결리스트를 탐색하며 홀수번째 노드를 그 뒤의 노드와 바꿔주면 된다 → Sol1

Solution

1. 탐색

   탐색의 횟수를 저장하여 홀수번째 노드의 경우 그 뒤의 노드와 순서 변경

   /**
    * Example:
    * var li = ListNode(5)
    * var v = li.`val`
    * Definition for singly-linked list.
    * class ListNode(var `val`: Int) {
    *     var next: ListNode? = null
    * }
    */
   class Solution {
       fun swapPairs(head: ListNode?): ListNode? {
           val answer = ListNode(0)
           answer.next = head
           var idx = 1
           var cursor = answer
           while (cursor!!.next != null && cursor!!.next!!.next != null) {
               if (idx % 2 == 1){ // 홀수번째 노드
   								// 주석은 1 -> 2 -> 3 일 때, 노드의 순서 변경
                   val tmp = cursor!!.next!!.next // 2 
                   cursor!!.next!!.next = cursor!!.next!!.next!!.next // 1 -> 3
                   tmp!!.next = cursor!!.next // 2 -> 1
                   cursor!!.next = tmp // start -> 2
               }
               cursor = cursor!!.next
               idx++
           }
           
           return answer.next
   
       }
   }
   

   시간 복잡도:

   

Point