数据结构初阶leetcodeOJ题（二）
目录
第一题
思路：
第二题
思路
第三题
描述
示例1
思路
总结：这种类似的题，都是用快慢指针，相差一定的距离然后输出慢指针。
第一题
给你一个链表的头节点
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 输出：[]
方法一
思路：
快慢指针：一个指向目标结点，一个指向目标结点的前驱结点。用一个tmp保存pos->next.
free()掉目标结点。
分两种情况：如果只有一个节点或者要删除的结点是首元节点，那么这时pre为NULL，pos 指向pos；否则pre->next == pos；
struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode* pre = NULL;struct ListNode* pos = head;while(pos!=NULL){if(pos->val==val){struct ListNode* tmp = pos->next;free(pos);pos = tmp;if(pre==NULL){head = pos;}else{pre->next = pos;}}else{pre = pos;pos = pos->next;}}return head;
}方法二：
思想；
创建新链表，用尾插法，尾插法没有改变原指针的next指向所以不用保存next节点，
但是在free（）时要保存下一节点。
struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* cur = head;struct ListNode* newhead = NULL;struct ListNode* tail = NULL;while(cur!=NULL){if(cur->val!=val){if(newhead==NULL){newhead = tail = cur;}else{tail->next = cur;tail = cur;}cur = cur->next;}else{struct ListNode* tmp = cur ->next;free(cur);cur = tmp;}}if(tail)tail->next=NULL;return newhead;}
第二题
给你单链表的头结点
head，请你找出并返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
示例 1：
输入：head = [1,2,3,4,5] 输出：[3,4,5] 解释：链表只有一个中间结点，值为 3 。示例 2：
输入：head = [1,2,3,4,5,6] 输出：[4,5,6] 解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。
思路
用快慢指针：快指针一次走两个，慢指针一次走一个。这样他们的路程之间差二倍。所以输出慢指针，即输出中间节点。
struct ListNode* middleNode(struct ListNode* head) {struct ListNode* slow = head;struct ListNode* fast = head;while(fast!=NULL&&fast->next!=NULL){slow = slow ->next;fast = fast->next->next;}return slow;
}第三题
描述
输入一个链表，输出该链表中倒数第k个结点。
示例1
输入：
1,{1,2,3,4,5}复制返回值：
{5}
思路
用快慢指针：快指针比慢指针先走k步，然后两者在同时走。
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {// write code herestruct ListNode* pre =pListHead;struct ListNode* pos = pListHead;while(k--){if(pos!=NULL){pos = pos->next;}else{return NULL;}}while(pos!=NULL){pre = pre->next;pos = pos->next;}return pre;}总结：这种类似的题，都是用快慢指针，相差一定的距离然后输出慢指针。
第四题
给你单链表的头节点
head，请你反转链表，并返回反转后的链表。示例 1：
输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]示例 2：
输入：head = [1,2] 输出：[2,1]示例 3：
输入：head = [] 输出：[]提示：
- 链表中节点的数目范围是
[0, 5000]-5000 <= Node.val <= 5000进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
方法一
将节点之间的next翻转。
用三个指针的原因是，只用两个指针翻转时，会导致链表断裂，但是用第三个指针保存下一个节点这样链表就不会断裂。
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*///方法一
struct ListNode* reverseList(struct ListNode* head) {if(head==NULL)return NULL;struct ListNode* left = NULL;struct ListNode* right= head;struct ListNode* tmp = head->next;while(right!=NULL){right->next = left;left = right;right = tmp;if(tmp!=NULL)tmp = tmp->next;}return left;
}方法二
用头插法，注意头插法需要保存指针。尾插法不用保存指针。
错误总结
（1）注意头插是新结点指向头结点，然后在将新节点设置为头结点。而不是直接将新节点设置为头节点
（2）C语言赋值语句，左值是变量，将新节点设置为头结点。newnode = cur；这是头结点为cur
//方法二
struct ListNode* reverseList(struct ListNode* head)
{if(head==NULL)return NULL;struct ListNode* cur = head;struct ListNode* newhead = NULL;while(cur!=NULL){struct ListNode* next = cur ->next; //保存下一个cur->next = newhead;newhead = cur;cur = next;}return newhead;
}