[Swift 알고리즘] LeetCode - 206. Reverse Linked List

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

Reverse Linked List - LeetCode

 

풀이

단방향 링크드 리스트를 역순으로 뒤집어야 하는 문제입니다.

Easy 난이도 문제지만 평소 생각해보지 않던 문제라 포스팅합니다.

prev 없이 링크드 리스트 뒤집기는 안 해본거 같아서요!

 

기본적인 아이디어는 swap과 유사합니다.

 

1. node와 next 변수를 선언합니다

node는 cursor 역할을 하고 next는 node의 다음 노드입니다.

 

2. input 링크드 리스트를 탐색하며 노드를 Swap 합니다.

input 링크드 리스트를 돌면서 노드를 swap 합니다.

 

next의 next를 temp로 둡니다.

a, b를 swap할 때 a를 다른 곳에 저장해두는 것과 동일한 로직이에요.

 

next의 next를 node로 설정하고 node를 next로 설정합니다.

그럼 1번 노드 -> 2번 노드였던게 2번 노드 -> 1번 노드로 순서가 바뀝니다.

 

다음 순회를 위해 next를 temp로 설정합니다.

여기서 temp는 next의 next를 대입해두었기 때문에

next를 기존 next의 next로 바꾸는 것과 동일합니다.

쉽게 말해 기존 링크드 리스트에서 다음 노드로 이동한거에요.

 

항상 링크드 리스트는 prev를 이용해 역순으로 탐색했었는데요.

이런 방법도 있다는 걸 알게 해준 문제였습니다.

 

감사합니다!

전체 코드

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func reverseList(_ head: ListNode?) -> ListNode? {        
        var node = head
        var next = head?.next
        
        node?.next = nil
        
        while next != nil {
            let temp = next?.next
            next?.next = node
            
            node = next
            next = temp
        }
        
        return node
    }
}

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.