劍指offer之打印鏈表的倒數(shù)第N個(gè)節(jié)點(diǎn)的值

1 問(wèn)題

打印鏈表的倒數(shù)第N個(gè)節(jié)點(diǎn)的值，（要求能只能便利鏈表一次）

比如鏈表如下，打印倒數(shù)第三個(gè)值就是4

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

 
2 思路

既然只要只能遍歷一次，我們可以這樣思考，比如我們要得到倒數(shù)第三個(gè)，那么它和尾巴的長(zhǎng)度就是3，我們可以這一節(jié)距離一直往左邊移動(dòng)，那么移動(dòng)最左邊的話，他們的開始是1，尾巴是3，所以我們搞2個(gè)指針進(jìn)行移動(dòng)就行，如下過(guò)程，就可以得到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

無(wú)非就是上面的逆過(guò)程，我們用代碼實(shí)現(xiàn)就行

 
3 代碼實(shí)現(xiàn)

    #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的大小長(zhǎng)度是否大于鏈表長(zhǎng)度
        //我們不能直接遍歷鏈表得到鏈表大小然后和n比較
        //那我們就用start->next != NULL來(lái)判斷也行
        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 運(yùn)行結(jié)果

the value is: 1

 
5 總結(jié)

請(qǐng)記住，2個(gè)指針像一把梭子，那樣在移動(dòng)，是那么的美妙，所以當(dāng)一個(gè)指針便利不了的時(shí)候，要記得用2個(gè)指針便利

然后還有類似的問(wèn)題，比如求鏈表的中點(diǎn)，鏈表長(zhǎng)度是奇數(shù)的時(shí)候，取中間的數(shù)字，如果鏈表長(zhǎng)度是偶數(shù)的話，取中間的2個(gè)都行，我們依然用2個(gè)指針，一個(gè)走一步，一個(gè)走2步，當(dāng)快的走完了的時(shí)候，慢的的走到中間了，切記。

 




 


作者：chen.yu
深信服三年半工作經(jīng)驗(yàn)，目前就職游戲廠商，希望能和大家交流和學(xué)習(xí),
微信公眾號(hào)：編程入門到禿頭 或掃描下面二維碼
零基礎(chǔ)入門進(jìn)階人工智能(鏈接)