问题

从1开始计数，计算倒数第k个结点的指针。例如：

思路

整着数到第k，然后前后一块往后走，前边的走到头，后边的极为倒数第k个结点，图示

注意

• 传入空指针
• k大于结点的个数

代码

ListNode* LastNNode(ListNode *root, int n){    if (root == NULL || n <=0)        return NULL;    ListNode *cur = root;    ListNode *pre = root;    int cnt = 0;    while (pre != NULL)    {        cnt++;        if (cnt == n)            break;        pre = pre->next;    }    if (cnt < n)    {        return NULL;    }    else    {        cur = root;        while (pre->next != NULL)        {            pre = pre->next;            cur = cur->next;        }        return cur;    }}

执行

#include 
      
       using namespace std;struct ListNode{    int val;    ListNode *next;    ListNode(int v) : val(v), next(NULL) {}};ListNode* LastNNode(ListNode *root, int n){    if (root == NULL || n <=0)        return NULL;    ListNode *cur = root;    ListNode *pre = root;    int cnt = 0;    while (pre != NULL)    {        cnt++;        if (cnt == n)            break;        pre = pre->next;    }    if (cnt < n)    {        return NULL;    }    else    {        cur = root;        while (pre->next != NULL)        {            pre = pre->next;            cur = cur->next;        }        return cur;    }}ListNode* createList(){    ListNode *root = new ListNode(0);    ListNode *p1 = new ListNode(1);    ListNode *p2 = new ListNode(2);    ListNode *p3 = new ListNode(3);    root->next = p1;    p1->next = p2;    p2->next = p3;    return root;}void deleteList(ListNode *root){    ListNode *p = root;    while(root != NULL)    {        p = root->next;        delete(root);        root = p;    }}void tranverse(ListNode* root){    while(root != NULL)    {        cout << root->val << " ";        root = root->next;    }    cout << endl;}int main(){    ListNode *root = createList();    root = NULL;    ListNode *p = LastNNode(root, 1);    cout << p << endl;    if (p != NULL)        cout << p->val << endl;         deleteList(root);}
      

 

推荐