求单向链表倒数第 k 个结点

题目:输入一个单向链表,输出该链表中倒数第 k 个结点。

传统做法是获取到链表的长度n,然后走n-k布,此方法弱爆了……

做法:

1、指定一个新的指针,走k步。如果k布之内就到了NULL,显然无倒数第k这说法,返回错误即可。

2、新指针到位后,和root一起next,知道新指针到了NULL。此时输出root指针当前的data即可。

int ll_last_k(struct Node* root, int k)
{
	// Make two ptr diff k distance
	struct Node* ptr = root;
	for(int i=0;i<k;i++)
	{
		if(ptr==NULL)
		{
			return -1;
		}
		ptr = ptr->next;
	}
	// Both next
	while(ptr!=NULL)
	{
		ptr = ptr->next;
		root = root->next;
	}
	return root->data;
}

 

Leave a Reply

Your email address will not be published.