[파이썬 알고리즘 인터뷰][연결리스트] 역순 연결 리스트

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

연결 리스트 뒤집기

 

책에서 구현된 코드

# 재귀
def reverseList(self, head: ListNode) -> ListNode:
    def reverse(node: ListNode, prev: ListNode = None):
        if not node:
            return prev
        next, node.next = node.next, prev
        return reverse(next, node)
        
    return reverse(head)
    
    
# 반복
def reverseList(self, head: ListNode) -> ListNode:
    node, prev = head, None
    
    while node:
        next, node.next = node.next, prev
        prev, node = node, next
    
    
    return prev

 

기억해야할 기법

• 재귀를 이용한 방법
  
  • 연결 리스트에서 재귀를 이용한 설계
  • 연결 리스트의 순서 변경
• 반복을 이용한 방법
  • 중복 선언시 새로운 변수 선언으로 진행하는 게 가독성이 좋은듯

 

내가 구현한 코드

def reverseList(head: ListNode) -> ListNode:
    node, reversed_list = head, None
    while node:
        next, node.next = node.next, reversed_list
        node, reversed_list = next, node

    return reversed_list

• 연결리스트에 코드 작성이 서투르듯하다
• 중복 선언 사용도 서투르다, 특히 연결 리스트에서 사용시