데이터 구조 단일 링크 된 목록

Question

단일 포인터로 연결된 포인터 안에 H가 있다고 가정하면 어떻게 의사 코드에서이 작업을 수행 할 수 있습니까? 단일 링크 된 목록에서 H가 가리키는 노드를 뒤집습니다. 참고 : 새 노드는 이 될 수 없습니다.

Answer 1

문제를 첫 번째 노드와 나머지 노드로 나누고 나머지 노드를 반전 한 다음 첫 번째 노드로 새 마지막 노드를 가리켜 반복적으로 풀 수 있습니다. 각 레벨의 재귀 스택이 당신이 당신의 의사에 포인터를 사용할 수있는 경우, 포인터를 사용하지 단순화

reverse(node header){ 

//Return if empty list. 
if (h == null) return 

//Split the problem into first and rest. 
node first = header.start 
node rest = first.next 

//Return if only one node. 
if (rest == null) return 

//reverse the rest of the problem, and then point the end of the rest to the old first. 
header.start = rest 
reverse(header) 
first.next.next = first 

//Set the old first to null, as it is now the last node in the list. 
first.next = null 

//Point the header H to the new first node. 
H.next = rest 

} 

호출 한 수준에서 "휴식"노드로 시작, 당신은 포인터를 전달할 수 있습니다 "재귀"노드는 각각의 후속 재귀 계층에 연결됩니다.