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

역순 연결 리스트

리트코드로 풀러가기

주어진 연결 리스트를 뒤집어라

입력
1->2->3->4->5->NULL

출력
5->4->3->2->1->NULL

---

reversedLinkedList.py

반복 구조

1. 이전 과정에서 prev는 이전의 결괏값(초기값 None)을 가리키고 있다.

2. head 노드를 temp로 참조하게 하고, head를 한칸 움직인다.

3. 그 뒤, 이전 노드를 가르키고 있는 temp의 next에 prev를 연결하게 되면 temp는 현재 이터레이션까지의 결과물(역순된 링크드 리스트의 첫 노드)이다.

4. 이터레이션의 첫 과정에서 prev는 이전의 모든 결과물을 담고 있어야 하므로, prev에 temp를 할당해준다.

이러한 과정을 head가 None이 될 때까지 반복하면 마지막의 prev값이 링크드 리스트의 역순이 된다.

def reverseList(self, head):
    """
    :type head: ListNode
    :rtype: ListNode
    """
    prev = None
    while head:

        temp = head
        head = head. next
        temp . next = prev
        prev = temp
    return prev

재귀 구조

다음 노드와 현재 노드를 피라미터로 지정한 함수를 계속하여 재귀 호출한다.

이 과정에서, 현재 node의 next에 이전의 노드와 계속 연결해주며 현재 node가 None이 될 때까지 재귀 호출한다.

def reverseList(head):
    def reverse(node, prev):
        if not node:
            return prev
        next, node.next = node.next, prev
        return reverse(next, node)

    return reverse(head)