精华内容
下载资源
问答
  • 链表中倒数第k个结点

    2020-12-22 16:31:26
    输入一个链表,输出该链表中倒数第k个结点 解题思路 本题的思路和之前看矩形那一题有相似之处,就是我们优先考虑边界情况,比如本题,我们需要查找链表中倒数第K个节点,那么想象此时身处链表最后的位置,我想要...
  • 链表中倒数第K个结点

    2019-10-08 14:36:11
    题目描述: 输入一个链表,输出该链表中倒数第k个结点。假设此链表中有6个结点,各结点的值分别是1、2、3、4、5、6。我们想要获取倒数第3个结点,即值为4。 思路:最易想到的解法是先走到链表的尾端,再从尾端回溯k...

    题目描述: 输入一个链表,输出该链表中倒数第k个结点。假设此链表中有6个结点,各结点的值分别是1、2、3、4、5、6。我们想要获取倒数第3个结点,即值为4。

    思路:最易想到的解法是先走到链表的尾端,再从尾端回溯k步,即得到倒数第k个结点。但是单向链表的结点只有从前往后的指针,没有从后往前的指针。但是,如果我们从前往后遍历链表直到尾端呢?假设整个链表有n个结点,那么倒数第k个结点就是从头结点开始的第n-k+1个结点。但是要获取到链表的结点个数n就要遍历链表,得到n之后再从头结点开始往后走n-k+1步即可。但是此方法需要遍历链表两次,第一次统计出链表的个数,第二次就能找到倒数第k个结点。最好的方法仅需遍历链表一次,思想如下:定义两个指针,第一个指针从链表的头指针开始遍历向后走k-1步,第二个指针保持不动;接下来,从第k步开始,两个指针同时向后移动,每次步长为一。由于两个指针的距离始终保持在k-1上,当第一个指针到达链表的尾部时,第二个指针正好到达倒数第k个结点。

    代码如下:

    #include <iostream>
    using namespace std;
    typedef struct ListNode
    {
        int data;
        ListNode* next;
        ListNode(int x) :data(x), next(NULL)
        {}
    }link;
    
    //打印链表
    void ShowList(link* head)
    {
        link* temp = head;
        while (temp)
        {
    	cout << temp->data << " ";
    	temp = temp->next;
        }
        cout << endl;
    }
    
    //找到链表倒数第K个结点
    link* FindKthToTail(link* head, unsigned int k)
    {
        if (head == NULL || k == 0)
        {
    	return NULL;
        }
        //定义俩指针
        link* p_Fast = head;
        link* p_Slow = head;
        for (unsigned int i = 0; i < k - 1; ++i)
        {
    	if (p_Fast->next != NULL)
    	{
    	    p_Fast = p_Fast->next;
    	}
    	else
    	{
    	    return NULL;
    	}
        }
        while (p_Fast->next != NULL)
        {
    	p_Fast = p_Fast->next;
    	p_Slow = p_Slow->next;
        }
        return p_Slow;
    }
    
    int main()
    {
        link head(1);
        link n1(2);
        link n2(3);
        link n3(4);
        link n4(5);
        link n5(6);
        head.next = &n1;
        n1.next = &n2;
        n2.next = &n3;
        n3.next = &n4;
        n4.next = &n5;
        ShowList(&head);
        unsigned int k = 3;
        link* temp = NULL;
        temp = FindKthToTail(&head, k);
        cout << temp->data << endl;
        return 0;
    }

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 18,929
精华内容 7,571
关键字:

链表中倒数第k个结点