一、问题描述
二、解题思路
方法一:计数器方式
- 最多遍历两次链表
- 时间复杂度 O (n)
- 空间复杂度 O（1）
- 先遍历链表，求出链表长度count
- 倒数第k个节点，就是正数第count-k+1个节点（下标为count-k）
- 再次遍历链表，找到该节点，返回数据
方法二:双指针方式
- 最多遍历一次链表
- 时间复杂度 O (n)
- 空间复杂度 O（1）
- 定义两个指针slow和fast，初始都指向第一个节点
- 初始fast指针先走k步
- 然后slow指针和fast指针每次各走一步，当fast指针指向空时，slow指针所指向的节点就是倒数第k个节点
- 返回该节点的数据
1.快慢指针初始位置
2.快指针先走k步
3.快指针走到NULL，慢指针走到倒数第k个节点
三、C语言代码实现
方法一:计数器方式
//返回单链表的倒数第 k 个节点 struct ListNode { int val; struct ListNode* next; }; typedef struct ListNode ListNode; //方式一 计数器方式 int kthToLast1(struct ListNode* head, int k) { ListNode* pcur = head;//遍历节点的指针 int count = 0; while (pcur)//求出链表长度 { pcur = pcur->next; count++; } pcur = head; count = count - k; while (count--)//找到该节点 { pcur = pcur->next; } return pcur->val; }
方法二:双指针方式
//方式二 快慢指针方式 int kthToLast2(struct ListNode* head, int k) { ListNode* slow = head, * fast = head; while (k--)//快指针先走k步 { fast = fast->next; } while (fast) { fast = fast->next; slow = slow->next; } return slow->val; }
