剑指offer之打印链表的倒数第N个节点的值

1 问题

打印链表的倒数第N个节点的值，（要求能只能便利链表一次）

比如链表如下，打印倒数第三个值就是4

1-> 2-> 3-> 4-> 5-> 6

 
2 思路

既然只要只能遍历一次，我们可以这样思考，比如我们要得到倒数第三个，那么它和尾巴的长度就是3，我们可以这一节距离一直往左边移动，那么移动最左边的话，他们的开始是1，尾巴是3，所以我们搞2个指针进行移动就行，如下过程，就可以得到4.

1   ->   2   ->   3   ->   4   ->   5  ->  6

start

end    

1   ->   2   ->   3   ->   4   ->   5  ->  6

start               end

 

1   ->   2   ->   3   ->   4   ->   5  ->  6

                                start              end

无非就是上面的逆过程，我们用代码实现就行

 
3 代码实现

    #include <iostream>
     
    using namespace std;
     
    typedef struct node
    {
        int value;
        struct node *next;
    } Node;
     
    void printN(Node *head, int n)
    {
        if (head == NULL || n <= 0)
        {
            std::cout << "head is NULL or n <= 0" << std::endl;
            return;   
        }
        Node *start = head;
        Node *end = head;
        //这里需要考虑n的大小长度是否大于链表长度
        //我们不能直接遍历链表得到链表大小然后和n比较
        //那我们就用start->next != NULL来判断也行
        for (int i = 0; i < n - 1; ++i)
        {
            if (start->next != NULL)
                start = start->next;
            else
            {
                std::cout << "the value of n is more than larger the length of list" << std::endl;
                return;
            }
        }
        while (start->next != NULL)
        {
            end = end->next;
            start = start->next;
        }
        std::cout << "the value is: " << end->value << std::endl;
    }
     
    int main()
    {
        Node *head = NULL;
        Node *node1 = NULL;
        Node *node2 = NULL;
        Node *node3 = NULL;
        head = (struct node*)malloc(sizeof(Node));
        node1 = (struct node*)malloc(sizeof(Node));
        node2 = (struct node*)malloc(sizeof(Node));
        node3 = (struct node*)malloc(sizeof(Node));   
        if (head == NULL || node1 == NULL || node2 == NULL || node3 == NULL)
        {
            std::cout << "malloc fail" << std::endl;
            return -1;
        }
        head->value = 0;
        head->next = node1;
     
        node1->value = 1;
        node1->next = node2;
     
        node2->value = 2;
        node2->next = node3;
     
        node3->value = 3;
        node3->next = NULL;
           
        printN(head, 3);
        free(head);
        free(node1);
        free(node2);
        free(node3);
        return 0;
       
    }

 
4 运行结果

the value is: 1

 
5 总结

请记住，2个指针像一把梭子，那样在移动，是那么的美妙，所以当一个指针便利不了的时候，要记得用2个指针便利

然后还有类似的问题，比如求链表的中点，链表长度是奇数的时候，取中间的数字，如果链表长度是偶数的话，取中间的2个都行，我们依然用2个指针，一个走一步，一个走2步，当快的走完了的时候，慢的的走到中间了，切记。

作者：chen.yu
深信服三年半工作经验，目前就职游戏厂商，希望能和大家交流和学习,
微信公众号：编程入门到秃头 或扫描下面二维码
零基础入门进阶人工智能(链接)