数据结构初阶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 here
struct 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;
}