数据结构（4）单链表算法题（上）

一、移除链表元素

1、题目描述

https://leetcode.cn/problems/remove-linked-list-elements

2、算法分析 

思路1：遍历链表找值为val的结点，执行删除指定位置数据的操作

        时间复杂度为O(N^2)，因此不提倡。

思路2：空间换时间

        创建新链表，遍历原链表，将值不为val的节点拿下来尾插

 

根据思路2，我们可以写出代码

typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) 
{//创建空链表ListNode* newHead = NULL;ListNode* newTail = NULL;ListNode* pcur = head;while(pcur){//把值不为val的结点尾插到新链表中if(pcur->val != val){//尾插//链表为空if(newHead == NULL){newHead = pcur;newTail = pcur;}else{//链表非空newTail->next = pcur;newTail = newTail->next;}}pcur = pcur->next;}//pcur为空return newHead;
}

 看似思路没有任何问题，但是OJ平台提示有一处解答出错 

这是什么原因呢？其实，我们并没有真的向系统申请新空间来创建新链表。newHead和newTail指针指向的都是pcur所指向的链表，当我们把5这个节点“尾插”下来之后，5这个节点的next指针仍然指向6这个节点，因此最后结果会多一个6出来。因此，我们需要把最后一个尾插的节点的next指针置为NULL，也就是newTail->next = NULL。但又带来一个问题，newTail指针不能为空，否则这行代码就是对空指针解引用，所以还要进行判断。

3、参考代码

/*** 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* pcur = head;while(pcur){//把值不为val的结点尾插到新链表中if(pcur->val != val){//尾插//链表为空if(newHead == NULL){newHead = pcur;newTail = pcur;}else{//链表非空newTail->next = pcur;newTail = newTail->next;}}pcur = pcur->next;}//pcur为空if(newTail)newTail->next = NULL;return newHead;
}

二、反转链表

1、题目描述

 https://leetcode.cn/problems/reverse-linked-list

 2、算法分析

思路1：创建新链表，遍历原链表，每个节点头插到新链表中。

        该思路很容易想到，代码实现也很简单，就不过多赘述，这里分享一个更优的解法~

思路2：创建三个指针

       创建三个指针n1，n2，n3。n1初始值为NULL，n2指向链表的头结点，n3指向n2的下一个结点。只要n2不为空，就把n2的next指针指向n1。接下来，n1指向n2，n2指向n3，n3指向n3的下一个节点。继续重复刚才的步骤，直到n2为NULL，此时n1就是反转之后的链表的头结点。

 3、参考代码

/*** 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;
}

三、链表的中间结点

1、题目描述

https://leetcode.cn/problems/middle-of-the-linked-list

 

2、算法分析 

思路1：求链表的总长度，总长度除以2求出中间节点的位置，返回中间位置的节点

        时间复杂度为O(N)，代码实现很简单，不做过多赘述，下面分享一个更优的解法~

思路2：快慢指针

 定义两个指针，初始值都指向头结点。慢指针（slow）每次走一步，快指针（fast）每次走两步。

3、参考代码 

/*** 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 && fast->next){slow = slow->next;fast = fast->next->next;}//fast为空或者fast->next为空就跳出循环return slow;
}

注意：while循环条件里的代码不可以写成fast->next && fast    ！！！    看似只是调换了一下顺序，但是两个代码会有很大的区别。因为此时循环条件会优先判断fast->next，当链表是偶数个节点时，fast指针为空时，此时fast指针为NULL，fast->next就是对空指针解引用，程序一定会报错。