링크 상용 조작 및 면접 문제

링크 는 비교적 기본 적 인 데이터 구조 로 acm 경기 에서 자주 사용 되 지 않 지만 면접 에서 자주 묻 기 때문에 꺼 내 서 써 보 니 많은 오류 가 발생 했 습 니 다. 조작 에 지침 이 많이 사용 되 기 때문에 자주 쓰 지 않 으 면 잘못 쓰기 쉽 습 니 다.
여기에 링크 의 생 성 을 적 었 습 니 다. 비교적 기본 적 입 니 다!그 다음 에 링크 의 요 소 를 삭제 하려 면 첫 번 째 요소 가 삭제 되 었 는 지 고려 해 야 합 니 다.그 다음 에 링크 의 마지막 k 번 째 요 소 를 찾 습 니 다. 두 개의 지침 을 사용 할 수 있 습 니 다. 한 개의 지침 을 사용 한 후에 k 번 을 옮 긴 다음 에 두 개 는 동시에 뒤로 갑 니 다. 먼저 k 번 을 걸 어서 끝까지 갈 때 다른 하 나 는 마지막 k 번 째 요소 에 이 르 렀 습 니 다. 두 지침 의 위 치 는 k 의 차이 가 있 기 때 문 입 니 다.마지막 으로 체인 시 계 를 반전 시 키 고 뒤로 가면 서 체인 시계의 바늘 을 앞의 요 소 를 가리 키 면 됩 니 다.
Notice: 1: 링크 는 노드 를 만 들 고 삭제 할 때 만 메모 리 를 분배 해 야 합 니 다. 즉, 메모 리 를 조작 할 때 필요 합 니 다. 이것 은 링크 분배 메모리 블록 이 연속 적 이지 않 고 분 산 된 것 입 니 다. 즉, 한 노드 의 한 노드 의 분배 이기 때문에 메모리 분배 함 수 를 호출 해 야 합 니 다.메모리 할당 함수 가 자주 사용 하 는 것 은 두 개의 C + + 중의 new 와 C 언어 중의 malloc 입 니 다. 이것 도 면접 에서 자주 묻 는 것 입 니 다. 즉, 그 차이 입 니 다.호출 방법 은 간단 하지만,

ListNode *node = new ListNode();
ListNode *node = (ListNode *)malloc(sizeof(ListNode));

물론 메모리 방출 을 잊 지 마 세 요. 해당 하 는 delete 와 free 는 다음 과 같 습 니 다.

delete node;
free(node);

그들 두 사람 은 어떤 차이 가 있 습 니까?1: now 지정 한 형식의 지침 을 되 돌려 줍 니 다. 할당 할 메모리 의 크기 를 자동 으로 계산 할 수 있 습 니 다.malloc 는 실제 유형 으로 강제로 전환 하고 크기 는 우리 가 줘 야 한다.2: malloc 는 메모리 만 분배 하고 그 값 을 초기 화하 지 않 습 니 다. 즉, 값 은 무 작위 이 고 new 는 초기 화 할 수 있 습 니 다.
일부 연습 코드:

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

struct ListNode
{
    int val;
    ListNode * next;
};

ListNode* creat(int n)  //    
{
    ListNode *head  = new ListNode(), *p = new ListNode();
   // head = p = (ListNode *)malloc(sizeof(ListNode));
    scanf("%d",&p->val);
    p->next = NULL;
    head = p;
    for(int i=1;i<n;i++)
    {
        ListNode *tmp = new ListNode();
        //tmp = (ListNode* )malloc(sizeof(ListNode));
        scanf("%d",&tmp->val);
        tmp->next = NULL;
        p->next = tmp;
        p = p->next;  ///notice：    
    }
    return head;
}
void print(ListNode *head)   ///    
{
    while(head!=NULL){
        printf("%d ",head->val);
        head = head->next;
    }
    puts("");
}

ListNode* RemoveNode(ListNode *head,int num)
{
    ListNode *newhead = NULL;  //               
    newhead = head;  ///head       newhead tmp      
    if(newhead->val == num){  ///         
        head = head->next;
        return head;
    }
    ListNode *tmp = NULL;
    tmp = head;   //            
    while(newhead!=NULL)  //    
    {
        if(newhead->val == num){
            tmp->next = tmp -> next -> next;
            //delete tmp;       
            return head;
        }
        tmp = newhead;
        newhead = newhead->next;
    }
}
void Find_KthNode(ListNode *head,int k)  ///     k   
{
    ListNode *one = NULL,*two = NULL;
    one = head,two = head;
    while(one!=NULL && k--)
    {
        one = one->next;
    }
    while(one!=NULL)
    {
        one = one->next;
        two = two->next;
    }
    printf("Find last %dth secessful
");
    printf("%d
",two->val);
}
ListNode* ReverseList(ListNode *head)
{
    ListNode *p = head;
    ListNode *pre = NULL;
    while(p!=NULL)
    {
        ListNode *tmp = p->next;
        if(tmp==NULL)
            head = p;
        p->next = pre;
        pre = p;
        p = tmp;  ///Notice :     p = p->next    
    }
    return head;
}

int main()
{
    //freopen("Input.txt","r",stdin);
    int n;
    while(~scanf("%d",&n))
    {
        ListNode *head = creat(n);
        puts("Creat secessful");
        print(head);
        int num;
        scanf("%d",&num);
        head = RemoveNode(head,num);
        puts("ReMove secessful");
        print(head);
        scanf("%d",&num);
        Find_KthNode(head,num);
        head = ReverseList(head);
        //printf("HEAD->%d
",head->val);
        print(head);
    }
    return 0;
}
/***** 10 1 2 3 4 5 6 7 8 9 10 10 3 ******/