チェーンテーブルの最後からK番目のノードを削除

この問題を見て私が先に考えたのは、チェーンテーブルの最後からK番目のノード(チェーンテーブルを1回だけ巡回することが要求されている)を検索し、削除すると別の面接問題です.チェーンテーブルのposノードを削除します.もう一つはOJで実現する方法である.
関連リンク表面接問題:C言語実現単鎖表面試験問題―基礎編https://blog.csdn.net/qq_37941471/article/details/78033970C言語は単鎖表面試験問題を実現する―段階的に進むhttps://blog.csdn.net/qq_37941471/article/details/80437143
コード実装:

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <windows.h>
#include <assert.h>

typedef int DataType;
typedef struct ListNode
{
    DataType data;//       
    struct ListNode* next;//     
}ListNode;

ListNode* BuyNode(DataType x)//    
{
    ListNode* Node = (ListNode*)malloc(sizeof(ListNode));//    
    Node->data = x;
    Node->next = NULL;
    return Node;
}

void PrintList(ListNode *plist)//    
{
    ListNode* cur = plist;
    while (cur)
    {
        printf("%d->",cur->data);
        cur = cur->next ;
    }
    printf("NULL
");
}
void PushFront(ListNode **pplist,DataType x)//  
{
    assert(pplist);
    //1.     
    //2.   
    if( *pplist == NULL )
    {
        *pplist = BuyNode(x);
    }
    else //   
    {
        ListNode* Node = BuyNode(x);
        Node->next = *pplist;
        *pplist = Node;
    }
}
void PopFront(ListNode **pplist)//  
{
    assert(pplist);
    //1.     
    //2.     
    //3.    
    if( *pplist == NULL )
        return;
    else if ( (*pplist)->next == NULL )
    {
        free(*pplist);
        *pplist = NULL;
    }
    else//   
    {
        ListNode* tmp  = *pplist;
        ListNode* Next = (*pplist)->next ;
        *pplist = Next;
        free(tmp);
    }
}
void PopBack(ListNode **pplist)//  
{
    assert(pplist);
    //1.     
    //2.     
    //3.     
    if( *pplist == NULL )
        return;
    else if( (*pplist)->next == NULL )
    {
        free(*pplist);//malloc free()
        *pplist = NULL;
    }
    else//   
    {
        ListNode* prev = *pplist;
        ListNode* cur = *pplist;
        while( cur->next )
        {
            prev = cur;
            cur = cur->next ;
        }
        free(cur);
        cur = NULL;
        prev->next = NULL;
    }
}
void Erase(ListNode **pplist,ListNode *pos)//  pos  
{
    assert(pplist&&pos);
    //1.   
    //2.   
    //3.    
    if( *pplist == pos )//  
    {
        PopFront(pplist);
    }
    else if( pos->next == NULL ) //  
    {
        PopBack(pplist);
    }
    else //   
    {
        ListNode* prev = *pplist;
        while( prev->next != pos )
        {
            prev = prev->next ;
        }
        prev->next = pos->next ;
        free(pos);
        pos = NULL;
    }
}
ListNode* FindKNode(ListNode* plist,int k)
{
    ListNode* slow = plist;
    ListNode* fast = plist;
    int count = k;
    assert(plist);
    if( plist == NULL || k <=0 )
        return NULL;
 //     n ，         ，      ，          
    while( --count > 0){//n-- n ，--n n-1 ,   n-1    n   
        fast = fast->next;
    }
    while( fast->next ){
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}
void test()//       K   
{
    ListNode* list = NULL;

    PushFront(&list,4);
    PushFront(&list,3);
    PushFront(&list,2);
    PushFront(&list,1);
    PrintList(list);

    Erase(&list,FindKNode(list,2));//     2   
    PrintList(list);
}
int main()
{
    test();
    return 0;
}

OJで実現:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *removeNthFromEnd(ListNode *head, int n) {
        //           n   ，    pos 
        //1.         n           
        if( head == NULL || n <= 0 )
            return NULL;
        ListNode* slow = head;
        ListNode* fast = head;
        //     n ，         ，      ，          
        while( --n > 0){//n-- n ，--n n-1 ,   n-1    n   
            fast = fast->next;
        }
        ListNode* prev = NULL;
        while( fast->next ){
            prev = slow;
            fast = fast->next;
            slow = slow->next;
        }
        //2.   pos ，slow        
        if( slow == head ){//  
            head = head->next;
        }
        else{
            prev->next = slow->next;
        }
        return head;
    }
};

VSでコードをテストします.

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <windows.h>
#include <assert.h>

typedef int DataType;
typedef struct ListNode
{
    DataType data;//       
    struct ListNode* next;//     
}ListNode;

ListNode* BuyNode(DataType x)//    
{
    ListNode* Node = (ListNode*)malloc(sizeof(ListNode));//    
    Node->data = x;
    Node->next = NULL;
    return Node;
}

void PrintList(ListNode *plist)//    
{
    ListNode* cur = plist;
    while (cur)
    {
        printf("%d->",cur->data);
        cur = cur->next ;
    }
    printf("NULL
");
}
void PushFront(ListNode **pplist,DataType x)//  
{
    assert(pplist);
    //1.     
    //2.   
    if( *pplist == NULL )
    {
        *pplist = BuyNode(x);
    }
    else //   
    {
        ListNode* Node = BuyNode(x);
        Node->next = *pplist;
        *pplist = Node;
    }
}
ListNode* removeNthFromEnd(ListNode *head, int n) {
        //           n   ，    pos 
        //1.         n           
        ListNode* prev = NULL;
        ListNode* slow = head;
        ListNode* fast = head;
        if( head == NULL || n <= 0 )
            return NULL;
        //     n ，         ，      ，          
        while( --n > 0){//n-- n ，--n n-1 ,   n-1    n   
            fast = fast->next;
        }
        while( fast->next ){
            prev = slow;
            fast = fast->next;
            slow = slow->next;
        }
        //2.   pos ，slow        
        if( slow == head ){//  
            head = head->next;
        }
        else{
            prev->next = slow->next;
        }
        return head;
    }
void test()//       K   
{
    ListNode* list = NULL;

    PushFront(&list,4);
    PushFront(&list,3);
    PushFront(&list,2);
    PushFront(&list,1);
    PrintList(list);

    list = removeNthFromEnd(list,2);
    PrintList(list);//     2   
}
int main()
{
    test();
    return 0;
}

“`