链表中倒数第 k 个结点, 反转链表

本贴最后更新于 807 天前,其中的信息可能已经天翻地覆

题目一:

输入一个链表, 输出该链表中倒数第 k 个结点.

时间限制:

1 秒

空间限制:

32768K

解题思路:

很容易想到的是求第 k 个结点, 其实倒数第 k 个结点稍微转换一下就出来了. 倒数第 k 个和正数第 k 个的相同点是前者距离尾部的长度和后者距离头部的长度是相同的.定义两个指针保持 k 这个长度一直向后移动, 知道 NULL 结点, 那么前面那个结点不就是倒数第 k 个结点吗? 但是细节方面需要考虑边界问题.

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
	ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
		ListNode* post = pListHead;
		ListNode* after = pListHead;
		
		int i = 0;
		for (;  after != NULL; i++) {
			if (i >= k) {
				post = post->next;
			}
			after = after->next;
		}
		/*考虑k值如果比链表长度都大*/
		return i < k ? NULL : post;
	}
}

题目二:

输入一个链表, 反转链表后, 输出新链表的表头.

时间限制:

1 秒

空间限制:

32768K

解题思路:

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...