검지 offer 알고리즘 문제

제목 1: 체인 테이블을 처음부터 끝까지 인쇄

제목 설명은 체인 테이블을 입력하고 끝에서 끝까지 체인 테이블의 각 노드의 값을 출력합니다.
사고방식 1: 귀속은head->next==NULL일 때 귀속을 중지하고 상부로 돌아가며 현재 노드 값을vector에 눌러 넣는다.마지막으로vect 전체를 되돌려줍니다.

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> res;
        if(head!=NULL){
            res = printListFromTailToHead(head->next);
            res.push_back(head->val);
        }
        return res;
    }
};

단점: 체인 테이블이 매우 길면 함수 호출의 층수가 깊어져 창고가 넘칠 수 있습니다.
사고방식 2: 비귀속
vector를 사용하면 흐르는 값이vector의 첫 부분에 놓입니다.

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> ret;
        while(head != nullptr)
        {
            ret.insert(ret.begin(),head->val);
            head = head->next;
        }
        return ret;
    }
};

단점:vector 머리에 데이터를 삽입할 때마다 함수 실행 효율이 낮음
사고방식 3:vector 정방향 저장소를 사용하고reverse

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> ret;
        while(head != nullptr)
        {
            ret.push_back(head->val);
            head = head->next;
        }
        reverse(ret.begin(),ret.end());
        return ret;
    }
};

사고방식 4: 창고를 보조로 하고 첫 번째 경험을 통해 값을 창고에 눌러 넣고 전체 체인 테이블을 모두 눌러 넣은 후에 창고 꼭대기에서 노드의 값을 하나씩 출력한다.

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> res;
        stack<int> temp;
        ListNode* p=head;
        while(p){
            temp.push(p->val);
            p = p->next;
        }
        while(!temp.empty()){
            res.push_back(temp.top());
            temp.pop();
        }
        return res;
    }
};

제목 2: 체인 테이블 중 꼴찌 k번째 결점

제목 설명은 체인 테이블을 입력하여 이 체인 테이블의 꼴찌 k번째 결점을 출력합니다.
사고방식1:stack을 사용하여 모든 노드를 저장하고 k-1개를 출력합니다. 이때 창고 꼭대기에 있는 것이 바로 k번째

class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        if(pListHead==NULL||k<=0)
            return NULL;
        stack temp;
        ListNode* p=pListHead;
        while(p!=NULL){
            temp.push(p);
            p=p->next;
        }
        if(temp.size()return NULL;
        for(int i=0; i1; i++){
            temp.pop();
        }       
        return temp.top();
    }
};

단점: 공간의 복잡도가 너무 높아 창고가 넘칠 수 있다.
사고방식 2: 두 개의 바늘을 먼저 첫 번째 바늘과 두 번째 바늘이 모두 머리 결점을 가리키게 한 다음에 첫 번째 손가락이 바로 (k-1)걸음을 해서 두 번째 k노드에 도달하게 한다.그리고 두 개의 바늘이 동시에 뒤로 이동한다. 첫 번째 결점이 끝에 도착했을 때 두 번째 결점이 있는 위치는 바로 꼴찌 k번째 노드이다.

class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        if(pListHead == NULL || k <= 0)
            return NULL;
        ListNode* p=pListHead;
        ListNode* q=pListHead;
        for(int i=0;i<k-1;i++){
            if(q->next != NULL)  // k 
                q = q->next;
            else
                return NULL;
        }
        while(q->next != NULL){
            p = p->next;
            q = q->next;
        }
        return p;
    }
};

제목 3: 체인 테이블 반전

제목은 체인 테이블을 입력하고 체인 테이블을 반전시킨 후 체인 테이블의 모든 요소를 출력하는 것을 설명합니다.
사고방식 1:stack을 새로 만들고 stack에 따라 창고를 열고 새 체인 테이블을 만듭니다.

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(pHead == NULL || pHead->next == NULL)
            return pHead;
        ListNode* pNew;
        stack temp;
        ListNode* p=pHead;
        while(p->next!=NULL){
            temp.push(p);
            p = p->next;
        }
        pNew = p;
        while(!temp.empty()){
            p->next = temp.top();
            p = p->next;
            temp.pop();
        }
        p->next = NULL;
        return pNew;
    }
};

방법 2: 세 개의 바늘이 동시에 미끄러진다. 첫 번째는 새로운 서열의 머리이고, 두 번째는 원래의 서열의 머리이며, 세 번째는 원래의 서열 머리의next
A->B->C->D->E->F(1)PB= A P = B PC = C(2) AD->E->F PB= B P = C PA = D(3)AE->F PB= C P = D PA = E...(N)ANULL PB = E P = F PA = NULL 종료 순환 P->next = PB PHead(A)->next = NULL NULL

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(pHead == NULL || pHead->next == NULL)
            return pHead;
        ListNode *pBefore = pHead, *p = pHead->next, *pAfter = p->next;
        while (pAfter) {
            p->next = pBefore; 
            pBefore = p;
            p = pAfter;
            pAfter = pAfter->next;
        }
        p->next = pBefore;
        pHead->next = NULL;
        return p;
    }
};

제목 4: 체인 테이블에서 중복된 결점 삭제

제목은 정렬된 체인 테이블에 중복된 결점이 있음을 설명합니다. 이 체인 테이블에서 중복된 결점을 삭제하십시오. 중복된 결점은 보존되지 않고 체인 헤더 바늘로 돌아갑니다.예를 들어 체인 테이블 1->2->3->3->4->4->5 처리 후 1->2->5
사고방식 1: 귀속

class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead)
    {
        if(pHead==NULL || pHead->next==NULL)
            return pHead;
        ListNode* current;
        if(pHead->val == pHead->next->val){
            current = pHead->next->next;
            while(pHead->val == current->val && current != NULL)
                current = current->next;
            return deleteDuplication(current);
        }
        else{
            current = pHead->next;
            pHead->next = deleteDuplication(current);
            return pHead;
        }
    }
};

사고방식 2: 비귀속

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead)
    {
        if(pHead==NULL || pHead->next==NULL)
            return pHead;
        ListNode*  newHead = new ListNode(-1); // ， -1 
        newHead->next = pHead;
        ListNode* pre = newHead;
        ListNode* p = pHead;
        ListNode* pNext = p->next;
        while(p!=NULL && p->next!=NULL){
            pNext=p->next;
            if(p->val == pNext->val){ 
                while(pNext!=NULL && pNext->val==p->val)
                    pNext = pNext->next;
                pre->next = pNext;  // ，pre ， 
                p = pNext;
            }
            else{ // ， pre , 
                pre = p;
                p = p->next;
            }   
        }
        return newHead->next;    
    }
};

제목 5: 두 개의 정렬된 체인 테이블 병합

제목은 두 개의 단조롭고 점차적으로 증가하는 체인표를 입력하고 두 개의 체인표가 합성된 체인표를 출력하는 것을 묘사한다. 물론 우리는 합성된 체인표가 단조롭고 줄지 않는 규칙을 만족시켜야 한다.
사고방식

class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        if(!pHead1 && !pHead2)
            return NULL;
        //  ， 
        if(!pHead1 || !pHead2)
            return(pHead1 == NULL)? pHead2:pHead1;
        ListNode* pNew;
        if(pHead1->val <= pHead2->val){
            pNew = pHead1;
            pNew->next = Merge(pHead1->next,pHead2);
        }
        else{
            pNew = pHead2;
            pNew->next = Merge(pHead1,pHead2->next);
        }
        return pNew;
    }
};

사고방식 2: 비귀속

class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        if(!pHead1 && !pHead2)
            return NULL;
        if(!pHead1 || !pHead2)
            return(pHead1 == NULL)? pHead2:pHead1;
        ListNode* pNew;  // 
        if(pHead1->val<=pHead2->val){
            pNew=pHead1;
            pHead1=pHead1->next;
        }
        else{
            pNew=pHead2;
            pHead2=pHead2->next;
        } 
        ListNode* p = pNew; // 
        while(pHead1 && pHead2){  // 
            if(pHead1->val < pHead2->val){
                p->next = pHead1;
                pHead1 = pHead1->next;
                p = p->next;
            }
            else{
                p->next = pHead2;
                pHead2 = pHead2->next;
                p = p->next;
            }
        }
        if(pHead1 == NULL)           // 1 
            p->next = pHead2;   
        if(pHead2 == NULL)           // 2 
            p->next = pHead1;    
        return pNew;
    }
};

제목 6: 복잡한 체인 테이블의 복제

제목 설명은 복잡한 체인 테이블 (각 노드에 노드 값과 두 개의 바늘이 있는데, 하나는 다음 노드를 가리키고, 다른 하나는 특수한 바늘이 임의의 노드를 가리킨다) 을 입력하고, 결과는 복사된 복잡한 체인 테이블의head로 되돌아옵니다.(출력 결과에서 매개 변수의 노드 인용을 되돌려 주지 마십시오. 그렇지 않으면 판정 프로그램이 비어 있습니다.)
문제 풀이 사고방식(1) 낡은 체인 테이블(예를 들어 A-B-C-D)에서 새 체인 테이블(A-A'-B'-C'-D')을 만들 때 새 체인 테이블의 특수 지침을 처리하지 않습니다.(2) 낡은 체인 시계의 특수 바늘에 따라 새로운 체인 시계의 특수 바늘을 복제한다.(3) 새 체인 테이블에서 복제 체인 테이블을 분리합니다.

/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead)
    {
        if(!pHead)
            return NULL;
        //  ， ，A-A'-B-B'-C-C'-D-D'
        RandomListNode *currNode = pHead; //curr = A
        while(currNode){
            RandomListNode *node = new RandomListNode(currNode->label); //  A'
            node->next = currNode->next; //A'->B
            currNode->next = node; //A->A'
            currNode = node->next; //curr = B ...... NULL
        }
        //  ， random 
        currNode = pHead;
        while(currNode){
            RandomListNode *node = currNode->next;
            if(currNode->random){
                node->random = currNode->random->next;
            }
            currNode = node->next;
        }
        //  ， 
        RandomListNode *pCloneHead = pHead->next;
        RandomListNode *tmp;
        currNode = pHead;
        while(currNode->next){
            tmp = currNode->next;
            currNode->next = tmp->next;
            currNode = tmp;
        }  // ，A->next = B;  ，A'->next = B';
        return pCloneHead;
    }
};