SearchListNode

发表于 分类于

题目描述[原题链接][https://www.acwing.com/problem/content/description/32/]

输入一个链表，输出该链表中倒数第k个结点。

注意：

  • k >= 0;
  • 如果k大于链表长度，则返回 NULL;

样例

1
2
3
输入：链表：1->2->3->4->5 ，k=2

输出：4

算法描述

定义一个结点，将它移动k个节点，然后头部再定义一个结点，之前的节点一起遍历，当之前的节点遍历到链表的结尾，后面的节点就是倒数第k个节点。操作过程中要注意的就是k的值可能比链表的长度还要大，需要特判一下；

C++代码

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* findKthToTail(ListNode* pListHead, int k) {
        if(pListHead==NULL)return NULL;
        auto p = pListHead;
        k--;
        while(k--&&p->next){
            p = p->next;
        }
        if(k>=0)return NULL;
        auto q = pListHead;
        while(p->next){
            p = p->next;
            q = q->next;
        }
        return q;
    }
};

Java代码

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode findKthToTail(ListNode pListHead, int k) {
        ListNode dummy=new ListNode(-1);
        dummy.next=pListHead;
        ListNode p = dummy;
        while(p.next!=null&&k>0){
            p=p.next;
            k--;
        }
        if(k!=0)return null;
        ListNode q = dummy.next;
        while(p.next!=null){
            p=p.next;
            q=q.next;
        }
        return q;
    }
}