菜鸟笔记
提升您的技术认知

《剑指Offer》链表中倒数第k个结点

阅读 : 630

题目描述:

  输入一个链表,输出该链表中倒数第k个结点。
  为了符合习惯,从1开始计数,即链表的尾结点是倒数第1个节点。例如,一个链表有6个结点,从头结点开始,它们的值依次是1,2,3,4,5,6。则这个链表倒数第三个结点是值为4的结点。

解题思路:

  对于单链表来说,没有从后向前的指针,因此一个直观的解法是先进行一次遍历,统计出链表中结点的个数n,第二次再进行一次遍历,找到第n-k+1个结点就是我们要找的结点,但是这需要对链表进行两次遍历。

  为了实现一次遍历,我们这里采用双指针解法。我们可以定义两个指针,第一个指针从链表的头指针开始先向前走k步,第二个指针保持不动,从第k+1步开始,第二个指针也从头开始前进,两个指针都每次前进一步。这样,两个指针的距离都一直保持在k,当快指针(走在前面的)到达null时,慢指针(走在后面的)正好到达第k个结点。注意:要时刻留意空指针的判断。

效果示意图,以链表总共6个结点,求倒数第3个结点为例:

链表中倒数第k个结点

除此之外,要注意代码的鲁棒性。需要判断传入参数合法性问题。

代码实现(c++)

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* findKthToTail(ListNode* pListHead, unsigned int k) {
        if(pListHead == NULL || k == 0){
            return NULL;
        }
        ListNode *pAhead = pListHead;
        ListNode *pBehind = pListHead;
        for(unsigned int i = 0; i < k - 1; i++){
            if(pAhead->next != NULL){
                pAhead = pAhead->next;
            }
            else{
                return NULL;
            }
        }
        while(pAhead->next != NULL){
            pAhead = pAhead->next;
            pBehind = pBehind->next;
        }
        return pBehind;
    }
};

代码实现(java)

   public ListNode FindKthToTail(ListNode head,int k) {
        if(head==null)
            return null;
        //思路:快慢指针,快指针先走k步,慢指针从头开始,都向前进,快指针到null时,前一个正好是倒数第k个
        ListNode fast=head,slow=head;
        for(int i=0;i<k;i++){ //快指针先走k步
            if(fast!=null)
                fast=fast.next;
            else
                return null;
        }
        while(fast!=null){ 
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }

笔记 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址