[Python][LeetCode] Insertion Sort List(삽입 정렬 리스트)

https://leetcode.com/problems/insertion-sort-list/description/

 

문제 설명:

연결리스트로 노드들이 주어졌을때 이것을 삽입정렬 방식으로 정렬하는 것이다.

head는 링크들로 연결된 노드들로 이루어져있다.

 

1. 더미노드를 만든다.

2. 더미노드에 다음노드로 head가 가르키는 노드 값을 새로운 노드로 만들어 next로 추가한다.

3. 더미노드에 포인터 p를 두어 p가 증가하면서 새로운 노드들이 위치 할 곳을 찾는다.

 

예시 [4,6,5,9,1]

test = ListNode(4, ListNode(6, ListNode(2, ListNode(9, ListNode(1)))))
Solution().insertionSortList_2(test)

 

• 더미노드는 지금 빈 노드를 가르키고 있다.
• 더미노드의 다음노드는 head가 가르키는 val 값을 새로운 노드로 만들어 가르키고 있다.
• head는 4를 가르켰지만 head.next 를 통해 6이 있는 곳으로 이동 

	dummy = ListNode()
        dummy.next = ListNode(head.val)
        head = head.next

 

 

 

• p는 더미노드를 가르키고 있고
• 새로운 노드는 head의 값을 새로운 노드로 만들어 가지고 있다.
• head는 다시 한 칸 이동
• 이 때 새로운 노드에는 6의 값을 가지고 있다.

 	while head:
            p = dummy
            new_node = ListNode(head.val)
            head = head.next

 

 

 

• p는 현재 4를 가르키고 있고 next는 없기 때문에
• 새로운 노드를 next로 연결시켜준다.

            if not p.next:
                p.next = new_node

 

 

• 다시 p는 더미노드쪽으로 이동시켜준다.
• 새로운 노드는 2의 값을 가지고 있으며
• head 는 그 다음 노드인 9를 가르키고 있다.
• p는 현재 4,6 노드를 가지고 있다.
• 4 < 2 는 성립이 안되기 때문에 else 조건문에 해당되어 2 -> 4 -> 6을 가르키게 된다.

        while head:
            p = dummy
            new_node = ListNode(head.val)
            head = head.next

            while p.next:
                if p.next.val < new_node.val:
                    p = p.next
                else:
                    new_node.next = p.next
                    p.next = new_node
                    break
            if not p.next:
                p.next = new_node

 

 

전체코드

    def insertionSortList_2(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode()
        dummy.next = ListNode(head.val)
        head = head.next

        while head:
            p = dummy
            new_node = ListNode(head.val)
            head = head.next

            while p.next:
                if p.next.val < new_node.val:
                    p = p.next
                else:
                    new_node.next = p.next
                    p.next = new_node
                    break
            if not p.next:
                p.next = new_node

        return dummy.next