DLL: Swap Nodes in Pairs (Advanced!)

👩‍💻 문제

You are given a doubly linked list.

Implement a method called swap_pairs within the class that swaps the values of adjacent nodes in the linked list. The method should not take any input parameters.

Note: This DoublyLinkedList does not have a tail pointer which will make the implementation easier.

Example:

1 <-> 2 <-> 3 <-> 4 should become 2 <-> 1 <-> 4 <-> 3

Your implementation should handle edge cases such as an empty linked list or a linked list with only one node.

Note: You must solve the problem WITHOUT MODIFYING THE VALUES in the list's nodes (i.e., only the nodes' prev and next pointers may be changed.)

 

 

가까운 애들끼리 스왑

 

💡 풀이

    def swap_pairs(self):
        dummy = Node(0)
        dummy.next = self.head
        before = dummy
        while self.head and self.head.next:
            first = self.head
            second = self.head.next
            before.next = second
            first.next, first.prev = second.next, second
            second.next, second.prev = first, before
            if first.next:
                first.next.prev = first
            self.head = first.next
            before = first #this was missed
        self.head = dummy.next
        if self.head:
            self.head.prev = None

 

 

✍️ 해설

바꿀 애들을 계속 head 로 설정해주고,

head 와 head.next 가 존재하는지를 확인해주고 (그래야 스왑하지, 아니면 그냥 냅두고 끝나니까)

head 와 head.next 를 first, second로 따로 설정해주는 것이 포인트!!

dummy를 설정해줘서 다시 맨 처음 head를 설정하는걸 가능하도록 하는 것도 중요

 

그림 그려가면서 노드가 잘 연결되는지 확인하고, head의 prev = None으로 설정해주는 것

 

 

🥳 배운점

dummy노드를 잘 써야겠다

first, second 등 어떤 특정 작업이 필요한 노드들에 대해 이름을 붙여주는 걸 무서워하지 말기

노드 바꾸는 과정에서 꼬이지 않도록 꼭 그림 그려가면서 확인하고, 누락되는 링크가 없도록 확인하기!