【Leetcode】面试题 02.02. 返回倒数第 k 个节点

【Leetcode】面试题 02.02. 返回倒数第 k 个节点

题目

实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。

注意：本题相对原题稍作改动

思路

• 设置双指针 pre cur 一开始都指向头节点

• 先让cur走K步 然后pre和cur之间的距离就是k 那么cur和pre同时走下去 直到cur走过尾节点 NULL

• 这时候 pre指向的就是倒数第k个节点

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    int kthToLast(ListNode* head, int k) {
        // 设置双指针 pre cur 一开始都指向头节点

        // 先让cur走K步  然后pre和cur之间的距离就是k  那么cur和pre同时走下去 直到cur走过尾节点 NULL

        // 这时候 pre指向的就是倒数第k个节点

        ListNode *pre = head,*cur = head;

        for(int i = 0; i < k; i++)
        {
            cur = cur->next;// 先走k步
        }

        while(cur != NULL)
        {
            pre  = pre->next;
            cur = cur->next;
        }

        return pre->val;

    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35