연결된 목록이 있다고 가정합니다. 목록을 오름차순으로 정렬해야 합니다.
따라서 입력이 [5, 8, 4, 1, 5, 6, 3]과 같으면 출력은 [1, 3, 4, 5, 5, 6, 8, ]
가 됩니다.이 문제를 해결하기 위해 다음 단계를 따릅니다.
- 값 :=새 목록
- 헤드:=노드
- 노드가 null이 아닌 동안 수행
- 값 끝에 노드 값 삽입
- 노드:=노드의 다음
- 목록 값 정렬
- values :=값의 요소를 취하여 이중 종료 큐를 만듭니다.
- 노드:=헤드
- 노드가 null이 아닌 동안 수행
- 노드 값:=큐의 왼쪽 요소 및 큐의 왼쪽에서 요소 삭제
- 노드:=노드의 다음
- 리턴 헤드
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
예
import collections
class ListNode:
def __init__(self, data, next = None):
self.val = data
self.next = next
def make_list(elements):
head = ListNode(elements[0])
for element in elements[1:]:
ptr = head
while ptr.next:
ptr = ptr.next
ptr.next = ListNode(element)
return head
def print_list(head):
ptr = head
print('[', end = "")
while ptr:
print(ptr.val, end = ", ")
ptr = ptr.next
print(']')
class Solution:
def solve(self, node):
values = []
head = node
while node:
values.append(node.val)
node = node.next
values.sort()
values = collections.deque(values)
node = head
while node:
node.val = values.popleft()
node = node.next
return head
ob = Solution()
head = make_list([5, 8, 4, 1, 5, 6, 3])
print_list(ob.solve(head)) 입력
[5, 8, 4, 1, 5, 6, 3]
출력
[1, 3, 4, 5, 5, 6, 8, ]