单链表算法题(一）（超详细版）

前言 : 通过算法题，学习解决问题的思路，再面对类似的算法题时，能快速定位解决方案

一 . 移除链表元素

移除链表元素 : . - 力扣（LeetCode）

思路一：

通过遍历链表找到值为val 的结点，执行指定位置删除 pos 位置结点的操作，这种算法的时间复杂度为 O(n^2) ，太高了，不是很优的算法，是否有可以降低时间复杂度的算法？

思路二 :

创建新的链表，遍历原链表，把不为val的值，尾插到新链表中 ---> 时间复杂度为 O(n)

1 . 创建新的空链表，链表是由结点构成的，创建链表就是创建结点 ( 头结点 newhead , 尾结点 newtail)

2 . 创建一个指针变量 pcur , pcur 为原链表的头结点，负责遍历原链表，获取不等val的结点，并把它赋给新链表

3 . 注意：如果我们按照1，2的思路写代码，会有一种特殊情况会报错，在下面中，会使用VS来进行调试！

碎碎念：如果在日常生活中，出现了报错，一定要兴奋起来，因为你又可以进步了，一定要耐下心来（看标红的报错），找出问题(BUG) , 分析问题（BUG），解决问题（BUG）

下面代码在 OJ 平台的测试中，有一个用例未通过，我们把这串代码 放在VS上，进行调试，找出BUG！ VS调试用起来

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){//pcur的值为val时，进行尾插到新链表中if (pcur->val != val){//空链表if (newhead == NULL){newhead = pcur;newtail = pcur;}//链表不为空else {newtail->next = pcur;newtail = newtail->next;}}pcur = pcur->next;}return newhead;
}void test3()
{//手动构造一个单链表SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));SLTNode* node5 = (SLTNode*)malloc(sizeof(SLTNode));SLTNode* node6 = (SLTNode*)malloc(sizeof(SLTNode));SLTNode* node7 = (SLTNode*)malloc(sizeof(SLTNode));node1->data = 1;node2->data = 2;node3->data = 6;node4->data = 3;node5->data = 4;node6->data = 5;node7->data = 6;node1->next = node2;node2->next = node3;node3->next = node4;node4->next = node5;node5->next = node6;node6->next = node7;node7->next = NULL;SLTNode* plist = node1;removeElements(plist, 6);
}
int main()
{//test1();//test2();test3();return 0;
}

因为结点5拿到新链表中进行尾插时，没有改变结点5本身的内容（数据+next指针），所以需要把next 指针置为 NULL;

单纯的置为NULL还不行 ：

需要保证在newtail 不为空时才能置为NULL，否则就是对空指针解引用，程序报错

/*** 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){//pcur的值为val时，进行尾插到新链表中if(pcur->val != val){//空链表if(newhead == NULL){newhead = pcur;newtail = pcur;}//链表不为空else{newtail->next = pcur;newtail = newtail->next;}}pcur = pcur->next;}
if(newtail)newtail->next = NULL;return newhead;
}

二 . 反转链表

反转链表:. - 力扣（LeetCode）

思路一：

创建新链表，遍历旧链表，把结点头插到新链表

思路二：

通过创建三个指针，把链表中的结点的指向改变

注意：

1 . n3 是先为NULL的，所以当n3 为NULL时，无需继续往后走 --> 用if 判断

2 . 当链表为空，对三个指针的初始化中的 n3( n3 = head->next) ---> 涉及了对NULL指针解引用，程序报错

/*** 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,*n2,*n3;n1 = NULL;n2 = head;n3 = head->next;while(n2){n2->next = n1 ;n1 = n2 ;n2 = n3 ;if(n3)n3 = n2->next;}return n1;
}

三 . 链表的中间结点

链表中间的结点 : . - 力扣（LeetCode）

链表结点个数分两种情况：奇数和偶数

思路一：

遍历链表，求结点总数/2 ---> 找到中间位置，返回中间位置的结点 ----> 时间复杂度O(n)

思路二：快慢指针（！！！）

！！！

满指针每次走一步，快指针每次走两步，链表个数为奇数时(fast->next == NULL）结束循环，链表个数为偶数时(fast == NULL）结束循环 , 基本思想：2*满指针 = 快指针，快指针走完链表时，满指针走到了链表的中间位置

注意：在循环条件的结束条件中， && 操作符两边的操作数不可以互换位置！！！

因为会出现对空指针解引用 --> 报错，而(fast && fast->next) ，当fast为NULL时，短路，不会再继续判断下一个条件了

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

四 . 合并两个有序链表

合并两个有序链表： . - 力扣（LeetCode）

思路1 ：

创建一个新链表(空链表) ，遍历两个旧的链表 , 比较值，值较小的往新链表尾插

1 . 创建新链表

2 . 创建两个指针变量(结点地址）分别指向 list1,list2 ;

3 . 比较两个结点指向的 val 值 ，值小的往新链表中进行尾插，尾插前需要判断新链表是否为空 (为空 --> 头尾结点都指向val值，不为空 ---> 新链表的尾结点指向val值)

思路一的代码中，有些代码重复率高，因为需要新链表为空的情况下需要特殊处理 , 思路二解决这个问题！

思路2 ：

创建一个新链表(非空链表--向操作系统申请一块空间，但是不存储任何有效值 --> “哨兵位") , 然后遍历两个旧链表，值较小的往新链表里进行尾插

坑点：

1 . 当链表存在空链表时，会涉及对空指针解引用，程序报错

2 . 当某一个链表先遍历完，但是另一个链表还有值没有遍历完，此时又不会再进入到循环体，就会存在数据丢失

思路一代码：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {if(list1 == NULL){return list2;}if(list2 == NULL){return list1;}ListNode* n1 = list1;ListNode* n2 = list2;ListNode* newhead ,*newtail;newhead = newtail = NULL;while(n1 && n2){//n1 的值比较小，n1的值尾插if(n1->val < n2->val){//空链表if(newhead == NULL){newhead = n1;newtail = n1;}//非空链表else{newtail->next = n1;newtail = newtail->next;}n1 = n1->next;}//n2 的值比较小，n2的值尾插else{//空链表if(newhead == NULL){newhead = n2;newtail = n2;}//非空链表else{newtail->next = n2;newtail = newtail->next;}n2 = n2->next;}}if(n1){newtail->next = n1;}if(n2){newtail->next = n2;}return newhead;
}

思路二代码：

1 . 思路二是对思路一的优化，起因是尾插数据的时候，需要判断链表是否为空，为空时的特殊处理使代码过于冗余，所以如果链表本身不为空，进行尾插就可以解决这种情况

2 . 初始化 ---> 通过向操作系统申请一块空间(malloc) ，但这个空间不存储有效值，只是占位置的作用 ---- "哨兵位"

3 .“哨兵位” 通过malloc 申请的空间，最后 free 掉，但此之前，需要把哨兵位的next 值存储起来，因为 next 值所代表的就是我们需要合并两个有序链表的新链表

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {if(list1 == NULL){return list2;}if(list2 == NULL){return list1;}ListNode* n1 = list1;ListNode* n2 = list2;ListNode* newhead ,*newtail;newhead = newtail = (ListNode*)malloc(sizeof(ListNode));while(n1 && n2){//n1 的值比较小，n1的值尾插if(n1->val < n2->val){newtail->next = n1;newtail = newtail->next;n1 = n1->next;}//n2 的值比较小，n2的值尾插else{newtail->next = n2;newtail = newtail->next;n2 = n2->next;}}if(n1){newtail->next = n1;}if(n2){newtail->next = n2;}ListNode* rethead = newhead->next;free(newhead);newhead = NULL;return rethead;
}

五 . 链表分割

链表分割 : 链表分割_牛客题霸_牛客网

思路 : 创建两个链表（大链表，小链表），然后遍历原链表，小于x值的结点 ----> 尾插到小链表中 ，把大于等于x 的结点尾插到大链表中 ，最后让小链表的尾结点和大链表的 ” 哨兵位 “ next 值的结点相连，最后返回小链表 " 哨兵位 ”的 next 值

坑点 : 如果大链表尾结点的next 值不置为 NULL ，这时如果 next 保存的值是链表某一结点的地址 ---> 陷入死循环 ---> 内存超限

1 . 创建四个指针变量，分别是大/小链表头结点/尾结点，并且初始化值（malloc向内存申空间 ---> 在后续尾插就不需要考虑链表为空情况，最后记得把小链表哨兵位的next值存储起来，释放空间）

2 . 创建指针变量，遍历原链表，判断与x的大小，进行尾插

3 . 把大链表的尾结点置为NULL ，避免死循环

4 . 大小链表连接

5 .存储需要返回的头结点的值

6 . free

7 . 置NULL

如果不把大链表的尾结点置NULL ，运行时会报错（内存超限）

---> 出现内存限制可能是时间复杂度太高 / 程序陷入死循环

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
#include <exception>
class Partition {public:ListNode* partition(ListNode* pHead, int x) {//创建两个非空链表 ： 小链表，大链表ListNode* lessHead, *lessTail;lessHead = lessTail = (ListNode*)malloc(sizeof(ListNode));ListNode* greaterHead, *greaterTail;greaterHead = greaterTail = (ListNode*)malloc(sizeof(ListNode));//遍历原链表，小于x 的尾插到小链表中，大于等于x 的尾插到大链表中ListNode* pcur = pHead;while (pcur) {//小链表if (pcur->val < x) {lessTail->next = pcur;lessTail = lessTail->next;}//大链表else {greaterTail->next = pcur;greaterTail = greaterTail->next;}pcur = pcur->next;}//避免循环 --> 大链表的尾指针要置为NULLgreaterTail->next = NULL;//大小链表首尾连接lessTail->next = greaterHead->next;ListNode* retHead = lessHead->next;free(lessHead);free(greaterHead);lessHead = NULL;greaterHead = NULL;return retHead;}
};