연결 목록이 있다고 가정하고 두 개의 값 i와 j도 있다고 가정하고 연결 목록을 i에서 j번째 노드로 바꿔야 합니다. 그리고 마지막으로 업데이트된 목록을 반환합니다.
따라서 입력이 [1,2,3,4,5,6,7,8,9] i =2 j =6과 같으면 출력은 [1, 2, 7, 6, 5, 4가 됩니다. , 3, 8, 9, ]
이 문제를 해결하기 위해 다음 단계를 따릅니다.
- prev_head :=null과 같은 값으로 노드를 가리키는 연결 목록 노드 생성
- 이전 :=prev_head, curr :=노드
- 0에서 i까지의 모든 값을 반복합니다. do
- prev :=curr, curr :=curr의 다음
- rev_before :=이전, rev_end :=현재
- 0에서 (j - i)까지의 모든 값을 반복합니다. do
- tmp :=curr의 다음
- curr의 다음:=이전
- 이전, curr :=curr, tmp
- rev_before의 다음 :=이전, rev_end.next :=현재
- prev_head의 다음 반환
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
예
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, i, j):
prev_head = ListNode(None, node)
prev, curr = prev_head, node
for _ in range(i):
prev, curr = curr, curr.next
rev_before, rev_end = prev, curr
for _ in range(j - i + 1):
tmp = curr.next
curr.next = prev
prev, curr = curr, tmp
rev_before.next, rev_end.next = prev, curr
return prev_head.next
ob = Solution()
head = make_list([1,2,3,4,5,6,7,8,9])
i = 2
j = 6
print_list(ob.solve(head, i, j)) 입력
[1,2,3,4,5,6,7,8,9], 2, 6
출력
[1, 2, 7, 6, 5, 4, 3, 8, 9, ]