시작 노드가 "head"이고 두 개의 정수 m과 n이 있는 연결 목록이 있다고 가정합니다. 우리는 목록을 순회하고 처음 m개의 노드가 목록에 유지되고 처음 m개의 노드가 삭제된 후 다음 n개의 노드와 같은 일부 노드를 삭제해야 합니다. 연결 리스트가 끝날 때까지 이 작업을 수행합니다. 헤드 노드에서 시작하여 수정된 연결 목록이 반환됩니다.
연결 리스트 구조는 다음과 같이 주어집니다. -
Node value : <integer> next : <pointer to next node>
따라서 입력이 요소 =[1, 2, 3, 4, 5, 6, 7, 8], m =3, n =1인 경우 출력은 [1, 2, 3, 5, 6입니다. , 7, ]
이 과정에서 3개의 노드 이후의 모든 노드가 삭제되므로 결국 연결 리스트는 아래와 같이 됩니다. -
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
이전 :=머리
-
커 :=머리
-
q :=0
-
피 :=0
-
curr이 null이 아닌 동안 수행
-
q :=q + 1
-
q가 m과 같으면
-
0에서 n 사이의 i에 대해 수행
-
curr.next가 null이 아니면
-
curr :=curr의 다음
-
-
-
이전의 다음 :=현재의 다음
-
q :=0
-
-
prev :=이전의 다음
-
curr :=curr의 다음
-
-
머리 반환
예제(파이썬)
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
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(']')
def solve(head, m, n):
prev = curr = head
q = 0
p = 0
while curr:
q += 1
if q == m:
for i in range(n):
if curr.next is not None:
curr = curr.next
prev.next = curr.next
q = 0
prev = prev.next
curr = curr.next
return head
head = ListNode()
elements = [1, 2, 3, 4, 5, 6, 7, 8]
head = make_list(elements)
res = solve(head, 3, 1)
print_list(res) 입력
[1, 2, 3, 4, 5, 6, 7, 8], 3, 1
출력
[1, 2, 3, 5, 6, 7,]