【数据结构】_链表经典算法OJ（力扣版）
目录
1. 移除链表元素
1.1 题目描述及链接
1.2 解题思路
1.3 程序
2. 反转链表
2.1 题目描述及链接
2.2 解题思路
2.3 程序
3. 链表的中间结点
3.1 题目描述及链接
3.2 解题思路
3.3 程序
1. 移除链表元素
1.1 题目描述及链接
原题链接：203. 移除链表元素 - 力扣（LeetCode）
题目描述：给你一个链表的头节点 head 和一个整数 val ，
请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
1.2 解题思路
思路1：创建一个新链表，遍历原链表，将 Node.val != val的结点均尾插到新链表中。
思路2：创建链表结点curNode遍历链表，并对应记录该结点的前驱结点与后继结点，删除该结点后再对其余结点进行链接。
1.3 程序
以思路1为例：
1、创建新链表首先定义一个结点作为新链表的头结点newHead，且须作为方法的返回值返回；
2、遍历原链表判断当前结点的val值，需定义一个结构体指针curNode用于遍历原链表。
3、由于需将Node.val !=val的结点尾插至新链表，故需定义结构体指针变量newTail指向新链表的最后一个结。并在最后完成尾插后将newTail的后继指针域置为NULL；
4、考虑特殊情况及相应处理：
（1）原链表为空：即head=NULL，导致curNode=NULL，不会进入第一个while循环，但在newTail->next=NULL 时会导致空指针解引用操作，出现错误。故需对newTail是否为空进行单独讨论处理。
（2）新链表为空：即原链表所有结点数据域的值都等于val，导致newTail->next=NULL 时会导致空指针解引用操作，出现错误。同（1）：需对newTail是否为空进行单独讨论处理。
处理逻辑为：
若newTail为空，再newTail->next=NULL，否则直接返回newHead（newHead也为空）；
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {
// 创建一个空链表
ListNode* newHead=NULL;
ListNode* newTail=NULL;
ListNode* curNode=head;
while(curNode){
if(curNode->val!=val){
// 情况1：链表为空
if(newHead==NULL){
newHead=curNode;
newTail=curNode;
}
// 情况2：链表不为空
else{
newTail->next=curNode;
newTail=newTail->next;
}
}
curNode=curNode->next;
}
// 将新链表尾结点的后继指针置空
// 讨论新链表为空与非空的两种情况
if(newTail){
newTail->next=NULL;
}
return newHead;
}2. 反转链表
2.1 题目描述及链接
题目链接：206. 反转链表 - 力扣（LeetCode）
题目描述：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
2.2 解题思路
思路1：
创建一个新的链表，并定义头结点指针newHead和尾结点指针newNode，遍历原链表，依次取当前结点头插到新链表中。
思路2：
无需创建新链表，创建三个指针，用于逐个逆转指针指向。
2.3 程序
以思路2为例：
创建三个指针变量。初始情况下，令n1指向空，n2指向原链表的头结点，n3指向原链表头结点的下一个结点。
以n2作为修改当前指向结点的后继指针域指向的用于遍历的结构体指针，逐个翻转指针域指向。再令n1、n2、n3依次后移。
考虑最终情况，n3最先变为空指针，直至n2指向原链表的最后一个结点完成指针域的指向反转后，表示当前链表已完成反转操作，故循环条件为n2不为空。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {
// 判空
if(head==NULL){
return head;
}
// 创建三个指针
ListNode* n1=NULL;
ListNode* n2=head;
ListNode* n3=n2->next;
while(n2){
n2->next=n1;
n1=n2;
n2=n3;
if(n3)
n3=n3->next;
}
return n1;
}3. 链表的中间结点
3.1 题目描述及链接
题目链接：876. 链表的中间结点 - 力扣（LeetCode）
题目描述：
给你单链表的头结点 head ，请你找出并返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
3.2 解题思路
思路1：
遍历原链表，使用count计数，count/2位置结点的下一个结点就是满足条件的中间结点，可返回count/2位置结点的后继指针即可。
思路2：快慢指针
创建两个结构体指针变量，令一个指针每次走一步，另外一个指针每次走两步，走得快的指针称为fast快指针，走得慢的指针称为slow慢指针。
3.3 程序
以思路二为例：考虑循环条件。
对于奇数个结点的链表，当fast->next=NULL时，slow正指向中间结点；
对于偶数个结点的链表，当fast=NULL时，slow正指向两个中间结点的后一个节点；
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {
ListNode* slow=head;
ListNode* fast=head;
while(fast!=NULL&&fast->next!=NULL){
fast=fast->next->next;
slow=slow->next;
}
return slow;
}注：对于循环条件while(fast!=NULL&&fast->next!=NULL)不可更改为
while(fast->next!=NULL&&fast!=NULL)，由于在偶数个结点的链表中，当fast==NULL时，slow正指向两个中间结点的后一个，此种情况下，若交换顺序则会导致对空指针的解引用，出错。
由于逻辑与具有短路特性，若已验证操作符左侧表达式为假，则不再验右侧表达式真假。