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

题目一:

输入一个链表, 输出该链表中倒数第 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

解题思路: