【经典算法】: 求链表中倒数第K个结点

客官°小女子只卖身不卖艺 2022-09-23 10:50 130阅读 0赞

链表中倒数第K个节点的求法  
方法有两个：  
1，先算出来链表中有多少个节点，假设为count个，然后顺序遍历  
找到count-k个时就可以截至

2，先对整个链表反序，然后倒过来找第K个即可

下面给出第一种方法：

static void GetKNumber(struct node** head_ref,int k){
        int count = 0,temp=0;
        struct node* head = *head_ref;
        struct node* head_trail = *head_ref;
        while(head!=NULL){
            count++;
            head = head->next;
        }
        while(head_trail!=NULL){
            temp++;
            if(temp-1==count-k){
                cout<<"the k data is"<<head_trail->data<<endl;
            }
            head_trail = head_trail->next;
        }
    }

上面是函数，然后下面是完整的程序：

#include <iostream>
    #include <stdio.h>
    #include <stdlib.h>
    using namespace std;
    struct node{
        int data;
        struct node* next;
    };
    void push(struct node** head_ref,int new_data){
        struct node* new_node = (struct node*) malloc(sizeof(struct node));
        new_node->data = new_data;
        new_node->next = (*head_ref);
        (*head_ref) = new_node;
    }
    
    
    
    static void reverse(struct node** head_ref){      //用于翻转，把所有的对应关系都反过来
        struct node* prev = NULL;
        struct node* current = *head_ref;
        struct node* next;
        while(current!=NULL){
            next = current->next;
    
            current->next = prev;     //倒过来指
            prev = current;
            current = next;  //用来将循环往后拖
        }
        *head_ref = prev;   //代表着最后一个
    }
    
    //链表中倒数第K个节点
    static void GetKNumber(struct node** head_ref,int k){
        int count = 0,temp=0;
        struct node* head = *head_ref;
        struct node* head_trail = *head_ref;
        while(head!=NULL){
            count++;
            head = head->next;
        }
        while(head_trail!=NULL){
            temp++;
            if(temp-1==count-k){
                cout<<"the k data is"<<head_trail->data<<endl;
            }
            head_trail = head_trail->next;
        }
    }
    
    
    
    void printList(struct node *head)
    
        {
    
            struct node *temp = head;
    
            while(temp != NULL)
    
            {
    
                printf("%d ", temp->data);
    
                temp = temp->next;
    
            }
    
        }
    int main(){
        struct node* head = NULL;
        push(&head,20);
        push(&head,4);
        push(&head,15);
        push(&head,85);
        push(&head,60);
        push(&head,100);
        printList(head);
        GetKNumber(&head,2);
        reverse(&head);
        cout<<endl<<"翻转后的结果"<<endl;
        printList(head);
        return 0;
    }