재귀와 비재귀를 이용한 단일 체인 반전에 대한 자세한 설명-PHP 튜토리얼-php.cn

재귀와 비재귀를 이용한 단일 체인 반전에 대한 자세한 설명

韦小宝

풀어 주다： 2023-03-21 11:44:02

원래의

1563명이 탐색했습니다.

이 글에서는 재귀와 비재귀를 사용하여 단일 체인 반전을 달성하는 방법을 설명합니다. 단일 체인 반전이 무엇인지 모르는 학생들이 많을 수 있으니, 헛소리는 그만하고 이 글을 직접 읽어보세요!
질문은 재귀 및 반복 알고리즘을 모두 사용할 수 있다는 힌트를 제공합니다.
재귀에 대한 깊은 이해가 없기 때문에 먼저 반복을 사용하여 알고리즘을 작성합니다. 질문의 헤드 노드는 데이터가 포함된 첫 번째 노드로 간주됩니다. 선두 노드를 역방향으로 순회하며, 노드 간 체인의 역전을 하나씩 순차적으로 구현합니다.
먼저 2개의 포인터를 사용하여 작업을 완료하려고 시도했지만 실패합니다

class Solution {
public:       
ListNode* reverseList(ListNode* head) { 
ListNode* pre = NULL;
  while(head -> next)
  {
 pre = head;
 head = head -> next;
 head -> next = pre; 
  }
  return head;
};

로그인 후 복사

이유는 다음과 같습니다. 반전 과정에서 head -> next가 반전되어 계속해서 뒤로 이동할 수 없으므로 포인터를 추가합니다. 3개의 포인터를 사용하여 완료되었습니다.

class Solution {
public:       
ListNode* reverseList(ListNode* head) { 
ListNode* pre = NULL;
  while(head)
  {
 ListNode* next = head -> next;
 head -> next = pre;//head是尾结点，指针置空
 head = next;
 pre = head; 
  }
  return pre;           //head = NULL
};

로그인 후 복사

작업은 재귀적으로 작동하지 않습니다. 이해하려면 토론을 참조하세요. 아이디어는 다음과 같습니다. 재귀를 통해 헤드 노드는 종료 조건(테일 노드에 도달한 후 중지)까지 계속해서 뒤로 이동합니다.

코드는 다음과 같습니다.

class Solution {
public:       
ListNode* reverseList(ListNode* head) { 
//终止条件，达到尾结点停止
if(head == NULL || head ==NULL)
return head;
else
{
//头结点向后移动
ListNode* temp = reverList(head->next);
head->next->next = head;   //1
head->next = NULL;         //2
}
return temp;
};

로그인 후 복사

재귀 종료 조건 도달 시 표시되는 상태

는 다음과 같습니다.

이전 수준의 재귀로 복귀한 후의 상태는 다음과 같습니다.

passed 코드 1과 2 두 줄을 주석 처리한 후 상태는 다음과 같습니다.

헤드 노드의 위치가 숫자와 관련이 있음을 알 수 있습니다. 반전 후의 헤드 노드인 temp는 절대 움직이지 않으므로 반전 턴 효과를 얻습니다. 재귀 코드를 이해할 수는 있지만 아직 디자인하는 방법을 모르고 여전히 멍청합니다. ㅋㅋㅋ