前面我们已经认识到了单链表，在具体的面试题中是怎么考察的呢？看完这些OJ讲解，或许你对链表会有新的认识！

目录

一、删除链表中值为val的结点

二、反转链表

三、寻找链表的中间结点

四、返回链表中倒数第k个结点

---

一、删除链表中值为val的结点

思路：我们可以遍历一遍链表，遇到val的结点我们就可以将其删除

注意特殊情况：1、当链表为空时

                         2、头结点就是要删除的结点

我们可以定义两个指针变量prev（previous）和cur（current），prev记录上一个结点的地址，cur表示当前位置地址

动图演示：

 代码如下：

struct ListNode{int val;struct ListNode *next;};
struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* prev=NULL,*cur=head;while(cur){if(cur->val==val){//prev可能为空指针解引用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;}}

 删除过程中应该记住，先指向再删除，因为先删除之后你就不能找到cur的下一个位置了

 

特殊情况下当val就是头结点，prev->next这里就是空指针的解引用，所以我们要进行头删处理

记录head的下一个结点的位置再进行删除

二、反转链表

 思路一：我们可以把链接关系反向，就相当于把链表给反转了

 

 为了方便操作，我们定义三个指针变量，分别是n1 n2 n3

n1：将要反转结点的前一个结点

n2：将要反转的结点

n3：将要反转结点的下一个结点

动图演示中间迭代过程：

结束条件分析可以知道，当图中n2=NULL时就停止了

代码如下：

struct ListNode 
{int val;struct ListNode *next;
};
struct ListNode* reverseList(struct ListNode* head)
{if(head==NULL)//因为后面head需要解引用所以必须要考虑链表为NULL的情况{return NULL;}ListNode*n1 = NULL;ListNode*n2 = head;ListNode*n3 = head->next;while(n2){n2->next = n1;n1 = n2;n2 = n3;//n2为NULL为循环结束条件，需保证n3不为NULL时，再迭代n3if(n3){n3 = n3->next;}}return n1;
}

 特殊情况：当传入空链表时，我们就不需要反转，直接返回NULL

                   当结束时，n3会提前到NULL，此时需要特判一下，预防野指针

思路二：我们可以利用头插法，创建一个新的结点newnode，把原来结点拿下来头插，最后返回newnode地址

动图演示：

 

 迭代结束的条件就是当cur走到NULL时就循环停止了

代码入下：

struct ListNode {int val;struct ListNode *next;
};struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* cur = head;//记录当前待头插的结点struct ListNode* newnode = NULL;//新链表初始时为空while (cur)//链表中结点头插完毕时停止循环{struct ListNode* next = cur->next;//记录下一个待头插的结点cur->next = newnode;//将结点头插至新链表newnode = cur;//新链表头指针后移cur = next;//指向下一个待头插的结点}return newnode;//返回反转后的头指针
}

三、寻找链表的中间结点

我们很容易想到，先遍历一遍找到结点总数，在遍历一遍找到结点的一半，这样时间复杂度就较高为 O(n^2),我们能不能将其优化到O(n)呢？

思路：用快慢指针fast（走两步）和slow（走一步），当fast=NULL时，slow就是中间结点，但我们还要考虑奇偶结点问题，仔细画图，当为偶数个结点时，结束条件就是fast的下个结点为NULL

 

动画演示：

奇数结点情况

 

 偶数结点情况：

代码如下：

struct ListNode {int val;struct ListNode *next;
};struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* fast = head;struct ListNode* slow = head;while (fast&&fast->next)//遍历继续的条件{slow = slow->next;//慢指针一次走一步fast = fast->next->next;//快指针一次走两步}return slow;//返回慢指针
}

 

四、返回链表中倒数第k个结点

思路：也是使用快慢指针，这里稍有不同点

1、fast先走k步

2、然后fast和slow一起走，直到fast走到NULL，那么slow就是倒数第k个结点

 动图演示：

 代码如下：

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) 
{struct ListNode*fast,*slow;fast=slow=pListHead;//fast先走k步while(k--){if(fast==NULL)//特判一下，当K大于链表长度时return NULL;fast=fast->next;}while(fast){fast=fast->next;slow=slow->next;}return slow;
}

需要注意特判一下的就是，当k大于链表长度时或者链表就是空链表时，我们的fast会越界访问，所以这里当fast=NULL时，我们直接return NULL;即可

 谢谢各位博友的观看！！