💕人生不满百，常怀千岁忧💕
作者：Mylvzi
文章主要内容：链表oj详解
题目一：移除元素
题目要求：
画图分析：
代码实现：
struct ListNode* removeElements(struct ListNode* head, int val){ struct ListNode*prev = NULL,*cur = head; //遍历 while(cur) { if(cur->val == val)//相等 { if(cur == head)//头删 { head = cur->next; free(cur); cur = head; } else//中间情况 { prev->next = cur->next; free(cur); cur = prev->next; } } else//不等 { prev = cur; cur = cur->next; } } return head; }
总结：
链表最大的特性就是其链接性，比如你要删除某个结点，为了保证其链接性，必须知道被删除结点的前一个结点，使其与被删除结点的下一个结点链接，所以解决此类问题需要两个指针:prev，cur
题目二：（快慢指针应用）
题目要求 :
画图分析：
代码实现：
struct ListNode* middleNode(struct ListNode* head){ struct ListNode*slow = head,*fast = head; //开始移动 while(fast && fast->next)//循环条件 { fast = fast->next->next;//一次移动两步 slow = slow->next; } return slow; }
题目三：求倒数第K个结点
题目要求：
画图分析：
代码实现：
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { struct ListNode*slow = pListHead,*fast = pListHead; //先让fast走k步，使相对距离为K while(k--) { //如果fast是NULL,证明链表没有K步长，就为空 if(fast == NULL) return NULL; fast = fast->next; } //一起前进，直到fast是尾结点 while(fast) { fast = fast->next; slow = slow->next; } return slow; }
总结：
快慢指针:
1.相对速度，fast一次走两步，slow一次走一步，fast到终点，slow刚好到中间位置（fast的位置要分奇偶，奇数fast走到韦结点即可，偶数fast走到Null）
2.相对路程，求倒数第k个，先让fast走k步，则fast和slow的相对距离一直是k，fast走到null，slow刚好走到倒数第k个
注意循环条件
题目四：合并两个有序链表
题目要求：
画图分析：
优化思路：（哨兵位）
代码实现：
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){ //如果有一个链表为空，直接返回另一个链表即可 if(list1 == NULL) return list2; if(list2 == NULL) return list1; //创建head和tail，便于进行尾插 struct ListNode* head = NULL,*tail = NULL; //思路：取小的尾插 while(list1 && list2)//有一个为空就推出 { if(list1->val < list2->val) { if(tail == NULL)//链表为空，直接复制 { head = tail = list1; } else//不为空，进行尾插 { tail->next = list1; tail = tail->next; } list1 = list1->next; } else { if(tail == NULL)//链表为空，直接复制 { head = tail = list2; } else//不为空，进行尾插 { tail->next = list2; tail = tail->next; } list2 = list2->next; } } //出循环，证明有一个已经遍历完 if(list1)//list1未遍历完 tail->next = list1; if(list2)//list1未遍历完 tail->next = list2; return head; } //带哨兵位解法 struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){ //如果有一个链表为空，直接返回另一个链表即可 if(list1 == NULL) return list2; if(list2 == NULL) return list1; //创建head和tail，便于进行尾插 struct ListNode* head = NULL,*tail = NULL; //创建哨兵位 head = tail =(struct ListNode*)malloc(sizeof(struct ListNode)); //思路：取小的尾插 while(list1 && list2)//有一个为空就推出 { if(list1->val < list2->val) { tail->next = list1; tail = tail->next; list1 = list1->next; } else { tail->next = list2; tail = tail->next; list2 = list2->next; } } //出循环，证明有一个已经遍历完 if(list1)//list1未遍历完 tail->next = list1; if(list2)//list1未遍历完 tail->next = list2; struct ListNode* del = head; head = head->next; free(del); return head; }
