[알고리즘] LinkedList 링크리스트: 활용 예제 - 뒤집기, 합치기, 가운데 값 찾기 - Kotlin

목차

 

저번 포스트에서는 LinkedList에 개념과 구현 방법을 다뤄봤는데요,

[Algorithm] Kotlin LinkedList 개념 - node 추가하기, 제거하기

이 포스트에서는 LinkedList로 가장 자주 활용되는 3가지 타입에 문제를 다뤄보겠습니다. 

 

 

LinkedList 뒤집기

아래 그림과 같이 LeetCode에 예제를 통해 LinkedList를 뒤집어 보겠습니다.

 

해설 - Reverse LinkedList(LeetCode)

 

fun reverseList(head: ListNode?): ListNode? {

	1. 
    var headNode = head

	while (head?.next != null) {
    2.
		val a = head
		val b = head.next
		val c = head.next?.next
	3.
		b?.next = headNode // 2 -> 1
	4.
    	a.next = c //       1 -> 3

	5.
		headNode = b
	}
,
	return headNode
}

 

1. 가장 앞에 있는 Node인 1을 headNode로 지정하게 됩니다. 그리고 아래 반복문을 head의 다음이 null이 아닐 때까지 반복합니다. 

 

2. 1->2->3은 a->b->c를 가리킵니다.

 

3. 현재 headNode는 a입니다. b.next는 headNode를 가리키게 합니다. 1 <-2.

 

4. a.next = c 이 코드는 head의 다음 값을 c로 나타냅니다. 1 -> 3.

 

4번까지 완료되면 아래와 같이 바뀝니다.

 

 

그리고 전체적으로 보면 이렇게 LinkedList가 변경됩니다. 

 

 

5.  b가를 headNode로 지정하게 되고. 3이 headNode가 되고 while문을 충족하기 때문에 다시 반복됩니다. 

 

 

LinkedList 가운데 위치 값 찾기

fast와 slow를 이용하여 가운데 값을 찾아보겠습니다. 원리는 이렇습니다. LinkedList head부터 fast가 2번 움직일 때마다 slow는 한번 움직입니다. 그리고 fast가 null에 도달했을 때 slow 값을 리턴합니다. 

 

해설 - Find middle form LinkedList(LeetCode)

 

fun findMiddle(head: ListNode?): ListNode? {

	var slow = head
    var fast = head 
    
    while(fast != null){
    	fast = fast.next
        if(fast != null){
        	fast = fast.next
            slow? = slow?.next
            
        }
    }
    return slow
}

 

2개의 LinkedList 합치기

 

아래 그림과 같이 2개의 LinkedList를 합치는데 오름차순으로 배열해서 합치도록 하겠습니다.

 

해설 - Merge Two Sorted Lists

 

/**
 * 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 mergeTwoLists(left: ListNode?, right: ListNode?): ListNode? {
        if (left == null) return right
        if (right == null) return left

        val (small, large) =
            if (left.`val` < right.`val`)
                left to right
            else
                right to left

        small.next = mergeTwoLists(small.next, large)
        return small
    }
}

 

 

 

참고

 

Explore - LeetCode

 

Explore - LeetCode

 

Announcing Data Structures & Algorithms in Kotlin, Second Edition!