[알고리즘][연결 리스트] - 3. 역순 연결 리스트

 

📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님'을 보고 작성되었습니다.

---

😎문제 : https://leetcode.com/problems/reverse-linked-list/

연결 리스트를 뒤집어라

---

[반복 구조로 뒤집기]

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        node, prev  = head,None

        while node:
            next, node.next = node.next, prev
            prev, node = node, next
        return prev

• node.next를 이전 prev 리스트로 계속 연결하면서 끝날 때까지 반복해주면 된다.
• node가 None이 될 때 prev는 뒤집힌 연결 리스트의 첫 번째가 된다..
• next, node.next = node.next, prev로 다중 할달하는 부분은 재귀나 반복 양쪽 모두 동일하다. 일부러 이름도 head가 node가 되도록 동일하게 맞췄다.
• 반복 풀이의 경우 prev에 node를, node에 next를 별로 셋팅하며 이를 이용해 node가 None이 될 때까지 계속 while 반복문을 돌게 된다.