Leetcode -剑指Offer 22.链表中倒数第k个结点

题目：输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例：
给定一个链表 : 1->2->3->4->5, 和 k = 2.
返回链表 4->5.

1. 暴力循环法

这个思路是用count计算链表的长度，返回倒数第k个结点，即是返回顺数第count-k个结点，再循环一次即可；

		struct ListNode* getKthFromEnd(struct ListNode* head, int k){if (head == NULL){return NULL;}//计算链表的长度struct ListNode* curr = head;int count = 0;while (curr){curr = curr->next;count++;}//k大于链表的长度，返回空if (k > count){return NULL;}//curr从头开始//返回倒数第k个，即是顺数count-k个curr = head;for (int i = 0; i < count - k; i++){curr = curr->next;}return curr;}

2. 双指针

这个思路是使slow指针和fast指针相差k步，当fast走到空时，slow即是倒数的第k个结点；

例如当k等于2：
初始化完成：

第一次循环完成：

最后完成：

代码：

		struct ListNode* getKthFromEnd(struct ListNode* head, int k){if (head == NULL){return NULL;}struct ListNode* slow = head, * fast = head;//使slow和fast相差k步for (int i = 1; i <= k; i++){//当到这里fast为空，证明k大于链表的长度，返回空（Leetcode这道题没有k大于链表长度的案例）if (fast == NULL){return NULL;}fast = fast->next;}//保证slow和fast相差k步，直到fast为空while (fast){slow = slow->next;fast = fast->next;}return slow;}

Leetcode -203.移除链表元素

题目：给你一个链表的头节点head和一个整数 val ，请你删除链表中所有满足Node.val == val的节点，并返回新的头节点 。

示例 1：
输入：head = [1, 2, 6, 3, 4, 5, 6], val = 6
输出：[1, 2, 3, 4, 5]

示例 2：
输入：head = [], val = 1
输出：[]

示例 3：
输入：head = [7, 7, 7, 7], val = 7
输出：[]

1. 递归

递归的思路是，直接找到递归的最深处，即链表的最后NULL，从后往前判断每个结点的val是否等于要移除的val，若某个结点的val等于要移除的val，就返回当前这个结点的next回去上一层；

这两句的含义如下图：

返回后上一个结点就是新的head，即如下图：

代码如下：

		struct ListNode* removeElements(struct ListNode* head, int val){//当链表为空时为最深处if (head == NULL){return NULL;}head->next = removeElements(head->next, val);return head->val == val ? head->next : head;}

2. 循环法

这个思路是直接循环寻找要移除的val，下面直接看代码和注释：

		struct ListNode* removeElements(struct ListNode* head, int val){//把头节点等于val的直接去掉，更新头结点为原来头结点的nextwhile (head != NULL && head->val == val){head = head->next;}//当head为空，返回空if (head == NULL){return NULL;}//curr从头开始遍历，判断curr的next的val是否等于要移除的val，是则更新curr的next；否则curr往后走struct ListNode* curr = head;while (curr->next){if (curr->next->val == val){curr->next = curr->next->next;}else{curr = curr->next;}}return head;}