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.
- 暴力循环法
这个思路是用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; }
- 双指针
这个思路是使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
输出：[]
- 递归
递归的思路是，直接找到递归的最深处，即链表的最后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; }
- 循环法
这个思路是直接循环寻找要移除的val，下面直接看代码和注释：
struct ListNode* removeElements(struct ListNode* head, int val) { //把头节点等于val的直接去掉，更新头结点为原来头结点的next while (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; }
