【数据结构】_链表经典算法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正指向两个中间结点的后一个，此种情况下，若交换顺序则会导致对空指针的解引用，出错。

由于逻辑与具有短路特性，若已验证操作符左侧表达式为假，则不再验右侧表达式真假。