Leetcode: Reverse Linked List, 연결 리스트 뒤집기

문제설명

• 단일 연결 리스트(Singly Linked List)의 노드를 역순으로 나열한 연결 리스트를 만든다.
• 재귀(recursive)와 반복(iterative) 방법이 있다.

문제풀이

• 반복문을 돌면서, 이전 값을 현재 가리키는 node의 next node로 할당한다.
• 옵셔널에 유의해야 한다. while 반복문을 돌며 옵셔널 바인딩을 사용하자.
• 반복문을 돌아 마지막에는 node 변수에 nil이 할당된다. 이 때, 마지막 반환 값이 nil이 되지 않도록 before 변수를 반환한다.

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; }
}
extension ListNode {
    func print() -> String {
        if let nextNode = next {
            return "\(val) -> \(nextNode.print())"
        } else {
            return "\(val)"
        }
    }
}

func reverseList(_ head: ListNode?) -> ListNode? {
    var node = head
    var before: ListNode? = nil

    while let n = node {
        let next = n.next
        n.next = before
        before = node
        node = next
    }
    return before
}

let n1 = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
print(n1.print())       // 1->2->3->4->5

let reversed = reverseList(n1)
print(reversed!.print()) // 5->4->3->2->1