회문 연결 목록 Leetcode 솔루션  


난이도 쉽게
자주 묻는 질문 어도비 벽돌 아마존 Apple 블룸버그 게시물에서 자본 하나 시스코 페이스북 서비스 구글 인텔 IXL Microsoft 뉴타 닉스 신탁 Paytm Snapchat 동네 짱 Yandex 주차
알고리즘 코딩 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions 연결된 목록 두 포인터

“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) 노드 자체의 값을 인쇄하기 전에 루트의 왼쪽 자식으로 이동하는 함수를 재귀 적으로 호출하기 때문입니다. 마찬가지로 우리는 재귀 마지막 노드로 먼저 이동하고 함수가 역 추적 할 때 노드 값을 역순으로 가져옵니다. 재귀의 영향을받지 않는 앞으로 반복하는 변수를 사용합니다. 이런 식으로 순방향 반복기의 값과 재귀로 얻은 역방향 노드의 값을 비교하여 요소를 비교할 수 있습니다.

참조
IP 주소 Leetcode 솔루션 해독

암호알고리즘

  1. 기능 isPalindrome () 목록이 있는지 여부를 반환하는 데 사용됩니다 머리 회문인지 아닌지
  2. 클래스의 데이터 멤버를 선언합니다. 앞 순방향 반복을위한 노드 저장
  3. In isPalindrom ():
    • 초기화 앞 = 머리
    • 회문을 반환 Check (head)
  4. In 회문 체크 (현재):
    • If 현재 is null로:
      • 반환 참된
    • If 회문 체크 (현재.다음) is 그릇된:
      • 반환 그릇된
    • If 현재 가치 is 지원 동일 앞값
      • 반환 그릇된
    • 앞쪽 증가 :
      • 앞 = 앞.다음
    • 반환 참된 우리가 모든 검사를 수행하면서
  5. 결과 인쇄

회문 연결 목록 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 메모리에 프레임을 스택합니다.

접근 (반대 반전)  

재귀에 사용 된 공간을 제거하는 유일한 방법은 주어진 목록을 제자리에서 수정하는 것입니다. 연결된 목록의 두 번째 절반을 뒤집은 다음 두 절반에 대해 두 개의 정방향 반복기를 사용하여 해당 값이 같은지 확인합니다. 이 프로세스를 위해 다음을 수행해야합니다.

  • 목록의 중간을 찾아서 후반부를 뒤집을 수 있습니다.
  • 목록의 후반부를 뒤집는 함수를 만듭니다.
  • 전반과 후반이 같은지 확인

위의 모든 작업은 선형 시간으로 수행 할 수 있습니다. 연결 목록을 뒤집은 후 후반부가 완료 될 때까지 확인을 시작합니다.

회문 연결 목록 Leetcode 솔루션

암호알고리즘

  1. If 머리 is null로:
    • 참을 돌려 주다
  2. 다음을 사용하여 연결된 목록의 중간을 찾습니다. middleOfList (머리기능:
    • 두 포인터 초기화 느리게빠른 둘 다 목록의 선두를 가리킴
    • 까지 fast.nextfast.next.next 둘 다 지원 없는:
      1. 증가 느리게 1 년까지 천천히 = slow.next
      2. 증가 빠른 2 년까지 빠른 = fast.next.next
    • 느리게 포인터는 이제 목록의 중간을 가리 킵니다.
    • 반환 느리게
  3. 이제 우리는 목록의 후반부를 뒤집습니다. reverseList (머리 = 중간.다음) 기능
    • 초기화 이전 = null로
    • 동안 머리 null이 아님 :
      • 다음 노드를 임시 변수에 저장하십시오. 다음 것
      • 사용하여 포인터 방향 반전 head.next = 이전
      • 이전 = 머리
      • 다음을 사용하여 목록에서 앞으로 이동 머리 = 다음
    • 반환 이전
  4. 이제 두 포인터를 초기화합니다. ptr1ptr2 두 반쪽을 반복하려면 :
    1. ptr1 = 머리
    2. ptr2 = 시작 후반의
    3. 동안 ptr2 null이 아님 :
      1. if ptr1.가치 같지 않다 ptr2.가치
        1. 반환 그릇된
    4. 반환 참된 전반과 후반에 모든 노드를 확인했기 때문에
  5. 결과 인쇄
참조
K 빈 슬롯 LeetCode

회문 연결 목록 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 = 목록의 크기.

참조
k보다 작거나 같은 모든 요소를 ​​결합하는 데 필요한 최소 스왑

공간 복잡성

O (1) 일정한 추가 공간 만 사용하므로