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

- 입력

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

- 출력

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

 

생각해 본것

1) 순서를 바꿔야 하므로 이걸 배열로 풀어서 바꿔보자.

2) 배열로 풀어서 다시 리스트로 넣는 방식

# 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) -> ListNode:
        q = []

        if not head:
            return head

        node = head
        # 리스트 변환
        while node is not None:
            q.append(node.val)
            node = node.next
        q = q[::-1]
        nodes = head
        while len(q) > 0:
            nodes.val = q.pop(0)
            nodes = nodes.next
        return head


def makeNode(lst):
    res = ptr = ListNode()
    for item in lst:
        ptr.next = ListNode(item)
        ptr = ptr.next

    return res.next


head = makeNode([1, 2, 3, 4, 5])
ans = Solution().reverseList(head)

while ans:
    print(ans.val, end=' ')
    ans = ans.next

 

처음에는 연결리스트를 배열로 반환해서 해봤다. 

책에 있는걸 봐보니 반복 구조로 뒤집기가 있었는데

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:


    def reverseList(self, head) -> ListNode:
        node, prev = head, None

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

        return prev


def makeNode(lst):
    res = ptr = ListNode()
    for item in lst:
        ptr.next = ListNode(item)
        ptr = ptr.next

    return res.next


head = makeNode([1, 2, 3, 4, 5])
ans = Solution().reverseList(head)

while ans:
    print(ans.val, end=' ')
    ans = ans.next

while node 문을 풀어보면

next = node.next
node.next = prev
prev = node
node = next

이렇게 된다. 저 next를 temp로 이름만 바꿔보자.

temp = node.next
node.next = prev
prev = node
node = temp

그러면 뭔가 보인다..

temp = a
a = b
b = c
c = temp

바로 swap 형식.. 

이렇게 풀어쓰니까 바로 눈에 보여 좋았다.

앞으로 순서가 바뀌는 문제가 있으면 이런 swap을 써보면 편할 것 같다.