剑指offer（14）——C++实现输出链表倒数第K个节点

亦凉 2021-10-29 07:08 113阅读 0赞

# 题目 #

输入一个链表，输出该链表中倒数第k个结点。

# 考察点 #

*  链表
 *  代码的鲁棒性

# 解题思路 #

*  一开始想法：遍历下链表，然后从后往前回溯K个节点，输出即可。但因给定链表为**单链表，其节点只有从前往后的指针**，故该想法行不通。
 *  输出倒数第K个节点，就是输出正数第N-K+1个，故先遍历一遍链表给出链表长度，再遍历到底n-k+1个节点，输出即可。
 *  只遍历一次的方法：设置两个指针，phead先走K-1步，然后pbehind跟它同步走，当phead刚好走到尾结点时，pbehind刚好走到n-k+1节点（即倒数第k个节点）

# 完整代码 #

/*14-输出链表倒数第K个节点*/
    #include<iostream>
    using namespace std;
    struct ListNode {
        
    	int val;
    	struct ListNode *next;
    	ListNode(int x) :
    			val(x), next(NULL) {
        
    	}
    };
    class Solution {
        
    public:
    	//遍历两次
    	ListNode* FindKthToTail01(ListNode* pListNode, unsigned int k) {
        
    		if (pListNode->next == NULL) return NULL;//注意返回值为NULL而不是0
    		if (k == 0) return NULL;
    
    		ListNode *pcount = pListNode;
    		unsigned int length = 0;
    		while (pcount != NULL)
    		{
        
    			pcount = pListNode->next;
    			length++;
    			
    		}
    		if (k > length) return NULL;
    		for (unsigned int i = 0; i < length - k + 1; i++)
    		{
        
    			pListNode = pListNode->next;
    		}
    		return pListNode;
    	}
    //遍历一次
    	ListNode* FindKthToTail(ListNode* pListNode, unsigned int k) {
        
    		ListNode* phead = pListNode;
    		ListNode* pbehind = pListNode;
    		if (pListNode == NULL || k == 0) return NULL;
    		for (int i = 1; i < k; i++)//先走k-1步
    		{
        
    			if (phead->next == NULL)
    				return NULL;
    			phead = phead->next;
    		}
    		while (phead->next != NULL)//不是phead!=NULL
    		{
        
    			phead = phead->next;
    			pbehind = pbehind->next;  
    		}
    		return pbehind;
    	}
    };
    
    int main()
    {
        
    	ListNode *p1 = new ListNode(5); ListNode *p2 = new ListNode(4); ListNode *p3 = new ListNode(3);
    	ListNode *p4 = new ListNode(2); ListNode *p5 = new ListNode(1);
    	p1->next = p2; p2->next = p3; p3->next = p4; p4->next = p5;
    	Solution s;
    	ListNode* result;
    	result = s.FindKthToTail(p1, 2);
    	cout << result->val << endl;
    	return 0;
    }

# 编程遇到的问题 #

*  循环条件：phead->next != NULL，不是phead!=NULL
 *  返回值：函数返回值要求什么返回什么，不能想当然
 *  int 是有符号整型，int类型和unsigned int 类型进行运算时要注意。