【数据结构与算法】返回单链表的倒数第 k 个节点_链表

目录

一、问题描述

二、解题思路

方法一:计数器方式

方法二:双指针方式

三、C语言代码实现

方法一:计数器方式

方法二:双指针方式

一、问题描述

【数据结构与算法】返回单链表的倒数第 k 个节点_链表_02

编辑

二、解题思路

方法一:计数器方式

  • 最多遍历两次链表
  • 时间复杂度  O  (n)
  • 空间复杂度  O（1）
  • 先遍历链表，求出链表长度count
  • 倒数第k个节点，就是正数第count-k+1个节点（下标为count-k）
  • 再次遍历链表，找到该节点，返回数据

【数据结构与算法】返回单链表的倒数第 k 个节点_链表_03

编辑

方法二:双指针方式

  • 最多遍历一次链表
  • 时间复杂度  O  (n)
  • 空间复杂度  O（1）
  • 定义两个指针slow和fast，初始都指向第一个节点
  • 初始fast指针先走k步
  • 然后slow指针和fast指针每次各走一步，当fast指针指向空时，slow指针所指向的节点就是倒数第k个节点
  • 返回该节点的数据

 1.快慢指针初始位置

【数据结构与算法】返回单链表的倒数第 k 个节点_双指针_04

编辑

2.快指针先走k步

【数据结构与算法】返回单链表的倒数第 k 个节点_链表_05

编辑

3.快指针走到NULL，慢指针走到倒数第k个节点

【数据结构与算法】返回单链表的倒数第 k 个节点_空间复杂度_06

编辑

三、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;
}