数据结构算法题（力扣）——链表

以下题目建议大家先自己动手练习，再看题解代码。这里只提供一种做法，可能不是最优解。

1. 移除链表元素（OJ链接）

题目描述：给一个链表的头节点 head 和一个整数 val ，删除链表中所有满足值等于 val 的节点，并返回新的头节点 。

解法：遍历链表，依次比对结点的值和val是否相等，相等则删除，不相等则更新指针指向，继续遍历。

这里需要分两种情况来讨论，一是链表结点的值都等于val，二是链表结点的值不都等于val。

struct ListNode* removeElements(struct ListNode* head, int val) 
{//全部结点的值都等于val或前面部分结点相等while(head&&head->val==val){head=head->next;}//删除全部结点后head为空或者链表本身就为空链表if(!head){return NULL;}struct ListNode* cur=head;while(cur->next){//cur的下一个结点值等于val，则删除下一个if(cur->next->val==val){cur->next=cur->next->next;}//不相等则cur后移一步else{cur=cur->next;}}return head;
}

无论链表结点中是什么样的值，当进行完第一个while循环后，如果head不是NULL，那么我们定义的cur指针指向的结点的值一定不等于val。因此第二个while循环里if的判断条件为cur->next->val==val，这样不需要保留cur的前一个结点，因为cur本身就是前一个结点（可能删除的结点的前一个结点）。

2. 反转链表（OJ链接）

题目描述：给定单链表的头节点 head ，反转链表，并返回反转后的链表的头节点。

我们所要做的操作如下图

如果链表为NULL，直接返回空即可。链表不为空，则需要反转。

以上图链表为例本题解法如下图所示。

当n2为空时，循环结束。

题解代码如下

struct ListNode* reverseList(struct ListNode* head)
{if(head==NULL){return NULL;}struct ListNode* prev=NULL;struct ListNode* cur=head;struct ListNode* next=head->next;while(cur!=NULL){cur->next=prev;prev=cur;cur=next;if(next){next=next->next;}}return prev;
}

注意题解中的prev，cur和next指针分别对应图中的n1，n2，n3。最后一步时n3为NULL，所以需要加判断语句。

3. 链表的中间结点（OJ链接）

题目描述：给定单链表的头结点 head ，请你找出并返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

如果链表结点个数为奇数，返回中间结点，如果结点数为偶数，返回第二个结点。比如有六个结点，则返回第四个结点。

解法：快慢指针法。指的是一个指针走的步数多，一个指针走的步数少。此题快指针走两步，慢指针走一步。当快指针走到NULL或最后一个结点时（链表结点数为偶数或奇数），慢指针指向的结点即为中间结点。

题解代码如下

struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* fast=head,*slow=head;while (fast!=NULL&&fast->next!=NULL){fast=fast->next->next;slow=slow->next;}return slow;
}

4. 合并两个有序链表（OJ链接）

题目描述：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

解法：创建两个指针变量分别指向两个链表的头，依次比较结点的值，值小的结点链接到新链表的尾，依次遍历链表，其中一个链表走完后，将剩余的链表链接到新链表的尾即可。

示例：

题解代码如下

typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {if (!list1) {return list2;}if (!list2) {return list1;}//分别指向两个链表的头结点ListNode *p1 = list1, *p2 = list2;//phead为新链表的头，ptail为新链表的尾ListNode *phead = NULL, *ptail = NULL;//两个链表都没有遍历完while (p1 && p2) {if (p1->val < p2->val) {//链接的是第一个结点if (phead == NULL) {phead = ptail = p1;p1 = p1->next;} else {ptail->next = p1;ptail = ptail->next;p1 = p1->next;}} else {//链接的是第一个结点if (phead == NULL) {phead = ptail = p2;p2 = p2->next;} else {ptail->next = p2;p2 = p2->next;ptail = ptail->next;}}}//链表1没有走完if (p1) {ptail->next = p1;}//链表2没有走完if (p2) {ptail->next = p2;}return phead;
}

5. 返回倒数第k个结点（OJ链接）

题目描述：给定一个单链表的头结点（head），找出单向链表中倒数第 k 个节点。返回该节点的值。

此题和第三题类似。解法依旧是快慢指针法。

解法：快指针先走k步，然后和慢指针一起走，快指针走到NULL时，慢指针指向的结点就是倒数第k个结点。
原理：快指针先走k步，使得两个指针间隔为k。再一起以相同速度走，最后两个指针间隔依旧是k。

题解代码如下

int kthToLast(struct ListNode* head, int k)
{struct ListNode* fast=head,*slow=head;while(k--){fast=fast->next;}while(fast){fast=fast->next;slow=slow->next;}return slow->val;
}

这里就先介绍这五个题的做法，大家可以试试用别的做法看是否可以做出来噢。