“Palindrome Linked List”문제에서 주어진 단일 정수가 연결 목록 회문인지 아닌지.
차례
예
List = {1 -> 2 -> 3 -> 2 -> 1}
true
설명 # 1: 목록은 처음과 뒤의 모든 요소가 값이 동일하기 때문에 회문입니다.
List = {1 -> 2 -> 3 -> 4 -> 5}
false
설명 # 2: 앞뒤의 요소가 동일하지 않으므로 목록은 회문이 아닙니다.
접근하다(재귀)
회문 속성을 확인하기 위해 배열의 뒷면에서 노드의 세부 정보가 필요하다는 것을 쉽게 알 수 있습니다. 이 경우 우리는 하나씩 연결 목록은 모든 노드에 도달하기 위해 앞으로 만 반복 할 수 있음을 의미합니다. 따라서 일부 데이터 구조를 사용하여 노드를 뒤에서 유지하는 것이 중요합니다. 스택 가장 최근 노드를 맨 위에 유지하므로 가능한 옵션입니다. 재귀도 비슷하게 사용할 수 있습니다. 재귀는 노드 값을 역순으로 가져 오는 데 우아합니다. 더 나은 이해를 위해 아래의 일반 의사 코드를 고려하십시오.
inorderTraversal(root)
{
if(root == null)
return;
inorderTraversal(root.left);
print(root.data);
inorderTraversal(root.right);
}
위의 코드는 먼저 인쇄합니다. 왼쪽 (left) 노드 자체의 값을 인쇄하기 전에 루트의 왼쪽 자식으로 이동하는 함수를 재귀 적으로 호출하기 때문입니다. 마찬가지로 우리는 재귀 마지막 노드로 먼저 이동하고 함수가 역 추적 할 때 노드 값을 역순으로 가져옵니다. 재귀의 영향을받지 않는 앞으로 반복하는 변수를 사용합니다. 이런 식으로 순방향 반복기의 값과 재귀로 얻은 역방향 노드의 값을 비교하여 요소를 비교할 수 있습니다.
암호알고리즘
- 기능 isPalindrome () 목록이 있는지 여부를 반환하는 데 사용됩니다 머리 회문인지 아닌지
- 클래스의 데이터 멤버를 선언합니다. 앞 순방향 반복을위한 노드 저장
- In isPalindrom ():
- 초기화 앞 = 머리
- 회문을 반환 Check (head)
- In 회문 체크 (현재):
- If 현재 is null로:
- 반환 참된
- If 회문 체크 (현재.다음) is 그릇된:
- 반환 그릇된
- If 현재 가치 is 지원 동일 앞값
- 반환 그릇된
- 앞쪽 증가 :
- 앞 = 앞.다음
- 반환 참된 우리가 모든 검사를 수행하면서
- If 현재 is null로:
- 결과 인쇄
회문 연결 목록 Leetcode 솔루션 구현
C ++ 프로그램
#include <bits/stdc++.h>
using namespace std;
struct listNode
{
int value;
listNode* next;
listNode(int x)
{
value = x;
next = NULL;
}
};
bool palindromeCheck(listNode* head)
{
if(head == NULL)
return true;
if(!palindromeCheck(head->next))
return false;
if(front->value != head->value)
return false;
front = front->next;
return true;
}
bool isPalindrome(listNode* head)
{
front = head;
return palindromeCheck(head);
}
int main()
{
listNode* head = new listNode(1);
head->next = new listNode(2);
head->next->next = new listNode(3);
head->next->next->next = new listNode(2);
head->next->next->next->next = new listNode(1);
cout << (isPalindrome(head) ? "true\n" : "false\n");
return 0;
}
자바 프로그램
class listNode
{
int value;
listNode next;
listNode(int x)
{
value = x;
next = null;
}
}
class palindrome_linked_list
{
static listNode front;
public static void main(String args[])
{
listNode head = new listNode(1);
head.next = new listNode(2);
head.next.next = new listNode(3);
head.next.next.next = new listNode(2);
head.next.next.next.next = new listNode(1);
System.out.println((isPalindrome(head)) ? "true" : "false");
}
static boolean palindromeCheck(listNode head)
{
if(head == null)
return true;
if(!palindromeCheck(head.next))
return false;
if(front.value != head.value)
return false;
front = front.next;
return true;
}
static boolean isPalindrome(listNode head)
{
front = head;
return palindromeCheck(head);
}
}
true
회문 연결 목록 Leetcode 솔루션의 복잡성 분석
시간 복잡성
의 위에) 재귀를 사용하여 목록을 한 번 탐색합니다. 여기서 N = 목록의 노드 수입니다.
공간 복잡성
의 위에) 재귀 함수를 호출하여 모든 노드 생성을 확인합니다. N 메모리에 프레임을 스택합니다.
접근 (반대 반전)
재귀에 사용 된 공간을 제거하는 유일한 방법은 주어진 목록을 제자리에서 수정하는 것입니다. 연결된 목록의 두 번째 절반을 뒤집은 다음 두 절반에 대해 두 개의 정방향 반복기를 사용하여 해당 값이 같은지 확인합니다. 이 프로세스를 위해 다음을 수행해야합니다.
- 목록의 중간을 찾아서 후반부를 뒤집을 수 있습니다.
- 목록의 후반부를 뒤집는 함수를 만듭니다.
- 전반과 후반이 같은지 확인
위의 모든 작업은 선형 시간으로 수행 할 수 있습니다. 연결 목록을 뒤집은 후 후반부가 완료 될 때까지 확인을 시작합니다.
암호알고리즘
- If 머리 is null로:
- 참을 돌려 주다
- 다음을 사용하여 연결된 목록의 중간을 찾습니다. middleOfList (머리) 기능:
- 두 포인터 초기화 느리게 및 빠른 둘 다 목록의 선두를 가리킴
- 까지 fast.next 및 fast.next.next 둘 다 지원 없는:
- 증가 느리게 1 년까지 천천히 = slow.next
- 증가 빠른 2 년까지 빠른 = fast.next.next
- 느리게 포인터는 이제 목록의 중간을 가리 킵니다.
- 반환 느리게
- 이제 우리는 목록의 후반부를 뒤집습니다. reverseList (머리 = 중간.다음) 기능
- 초기화 이전 = null로
- 동안 머리 null이 아님 :
- 다음 노드를 임시 변수에 저장하십시오. 다음 것
- 사용하여 포인터 방향 반전 head.next = 이전
- 이전 = 머리
- 다음을 사용하여 목록에서 앞으로 이동 머리 = 다음
- 반환 이전
- 이제 두 포인터를 초기화합니다. ptr1 및 ptr2 두 반쪽을 반복하려면 :
- ptr1 = 머리
- ptr2 = 시작 후반의
- 동안 ptr2 null이 아님 :
- if ptr1.가치 같지 않다 ptr2.가치
- 반환 그릇된
- if ptr1.가치 같지 않다 ptr2.가치
- 반환 참된 전반과 후반에 모든 노드를 확인했기 때문에
- 결과 인쇄
회문 연결 목록 Leetcode 솔루션 구현
C ++ 프로그램
#include <bits/stdc++.h>
using namespace std;
struct listNode
{
int value;
listNode* next;
listNode(int x)
{
value = x;
next = NULL;
}
};
listNode* middleOfList(listNode* head)
{
listNode *slow = head , *fast = head;
while(fast->next != NULL && fast->next->next != NULL)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
listNode* reverseList(listNode* head)
{
listNode *prev = NULL;
while(head != NULL)
{
listNode* next = head->next;
head->next = prev;
prev = head;
head = next;
}
return prev;
}
bool isPalindrome(listNode* head)
{
if(head == NULL)
return true;
listNode* middleNode = middleOfList(head);
listNode* startOfSecondHalf = reverseList(middleNode->next);
listNode *ptr1 = head , *ptr2 = startOfSecondHalf;
while(ptr2 != NULL)
{
if(ptr1->value != ptr2->value)
return false;
ptr1 = ptr1->next;
ptr2 = ptr2->next;
}
return true;
}
int main()
{
listNode* head = new listNode(1);
head->next = new listNode(2);
head->next->next = new listNode(3);
head->next->next->next = new listNode(2);
head->next->next->next->next = new listNode(1);
cout << (isPalindrome(head) ? "true\n" : "false\n");
return 0;
}
자바 프로그램
class listNode
{
int value;
listNode next;
listNode(int x)
{
value = x;
next = null;
}
}
class palindrome_linked_list
{
public static void main(String args[])
{
listNode head = new listNode(1);
head.next = new listNode(2);
head.next.next = new listNode(3);
head.next.next.next = new listNode(2);
head.next.next.next.next = new listNode(1);
System.out.println((isPalindrome(head)) ? "true" : "false");
}
static listNode middleOfList(listNode head)
{
listNode slow = head , fast = head;
while(fast.next != null && fast.next.next != null)
{
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
static listNode reverseList(listNode head)
{
listNode prev = null;
while(head != null)
{
listNode next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
static boolean isPalindrome(listNode head)
{
if(head == null)
return true;
listNode middleNode = middleOfList(head);
listNode startOfSecondHalf = reverseList(middleNode.next);
listNode ptr1 = head , ptr2 = startOfSecondHalf;
while(ptr2 != null)
{
if(ptr1.value != ptr2.value)
return false;
ptr1 = ptr1.next;
ptr2 = ptr2.next;
}
return true;
}
}
true
회문 연결 목록 Leetcode 솔루션의 복잡성 분석
시간 복잡성
의 위에) 선형 루프를 사용하여 목록의 중간을 찾고 뒤집고 두 반쪽을 비교합니다. 여기, N = 목록의 크기.
공간 복잡성
O (1) 일정한 추가 공간 만 사용하므로
