单链表OJ思路

目录

---

前言

        11道单链表OJ题的解题思路。

---

一、移除链表元素

链接：203. 移除链表元素 - 力扣（LeetCode）

思路：

1. 创建两个指针 newHead, newTail 指向新链表的头尾，这个新链表还是由原链表组成，只不过是去除了指定要删除的结点。
2. 再定义一个指针 pcur 去遍历原链表，与要删除的数据值 val 比较，只要不是要删除的结点，就尾插到新链表的尾部。
3. 细节：第一次尾插时需要注意，此时 newHead 和 newTail 都为空，需要将第一个结点分别赋值给 newHead 和 newTail。第二次及以上时就只需要尾插即可，插到 newTail 的 next 指针，插入后，newTail 需走到新结点位置为下一次插入做准备。
4. 还有一个需要情况需要注意：
5. 
6. 如图原链表中的最后一个结点是需要被删除的，可是在上述思路得到的新链表中，结点 5 的 next 指针指向的依旧是需要删除的结点 6，因此我们最后需要判断一下，如果尾结点 newTail 不为空，就将其 next 指针设置为 NULL。

代码：

typedef struct ListNode SLTNode;struct ListNode* removeElements(struct ListNode* head, int val) 
{SLTNode*newHead,*newTail;newHead=newTail=NULL;SLTNode*pcur = head;//pcur遍历while(pcur){//值不为val进行尾插if(pcur->val!=val){//第一次尾插if(newHead==NULL){newHead=newTail=pcur;}else{newTail->next=pcur;newTail=newTail->next;}}pcur=pcur->next;}//只要不是空链表就将尾结点的next指针置空if(newTail)newTail->next=NULL;return newHead;
}

---

二、反转链表

链接：206. 反转链表 - 力扣（LeetCode）

思路：

1. 反转单链表使用的是三指针法，即 pcur（指向头结点），prev（指向pcur的上一个结点），next（指向pcur的下一个结点）。
2. 
3. 注意 prev 第一次是指向 NULL。
4. 反转方法：pcur 用于遍历单链表并反转链表，next 提前储存 pcur 的下一个结点方便 pcur 遍历，prev 储存 pcur 的上一个结点方便 pcur 反转时找到上一个结点。操作顺序：首先初始化三指针，然后 pcur 修改当前结点的 next 指针指向 prev，再 prev 走到 pcur 位置，再将 pcur 移动到 next 位置，最后让 next 指针走到 pcur 的下一个结点。重复上述步骤直到 pcur 为空。
5. 最后 prev 刚好指向反转后的链表头结点，返回 prev 即可

代码：

typedef struct ListNode SLTNode;struct ListNode* reverseList(struct ListNode* head) 
{//三指针法SLTNode*prev = NULL;SLTNode*pcur = head;while(pcur){SLTNode*next = pcur->next;pcur->next=prev;prev=pcur;pcur=next;}return prev;
}

---

三、链表的中间结点

链接：876. 链表的中间结点 - 力扣（LeetCode）

思路：

1. 快慢指针法。定义一个 fast 指针每次移动两个结点，定义一个 slow 指针每次移动一个结点。
2. 当 fast 指针走完链表后，slow 指针指向的就是中间节点。
3. 可以想象有两人在同一起点围绕操场跑一圈，甲的速度为乙的两倍，甲跑完了，乙只跑了一半。
4. 唯一需要注意的细节就是循环结束的条件为 while(pcur && pcur->next)，即以下两种情况
5. 
6. fast 有两种情况会导致循环结束，一种即为 next 指针为空，此时不能连跳两个结点因为不能对空指针解引用。一种为 fast 已经为空。

代码：

typedef struct ListNode SLTNode;struct ListNode* middleNode(struct ListNode* head) 
{//快慢指针法SLTNode*prev=head;SLTNode*pcur=head;while(pcur && pcur->next){pcur=pcur->next->next;prev=prev->next;}return prev;
}

---

四、返回倒数第k个结点

链接：面试题 02.02. 返回倒数第 k 个节点 - 力扣（LeetCode）

思路：

1. 这题思路与快慢指针类似，既然要求倒数第k个结点，那我们先定义一个指针走k个结点，再定义一个指针指向链表头结点，然后让这两个指针一次走一个结点直到先走了k个结点的指针走到了空指针。那么另外一个指针的位置就是倒数第k个结点了。
2. 定义一个指针 pcur 走k个结点，再定义一个指针 prev 指向头结点。然后两指针都每次移动一个结点。
3. 
4. 最后结果：
5. 
6. 原理：可以想象两个人走路，同一起点，A先走了2步，那么B一开始就落后 A 2步，然后两人同时走路，保持一样的速度每秒一步，那么A走到了终点，B还差2步。

代码：

typedef struct ListNode SLTNode;int kthToLast(struct ListNode* head, int k) 
{SLTNode*prev=head;SLTNode*pcur=head;//pcur先走k步while(k--){pcur=pcur->next;}//同步走while(pcur){pcur=pcur->next;prev=prev->next;}return prev->val;
}

---

五、合并两个有序链表

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

思路：

1. 这题我个人是采取了类似归并排序的思路。代码写的有点冗余。
2. 简单点说定义三个指针 prev，pcur，newTail，prev用于遍历链表list1，pcur用于遍历链表list2，newTail为新链表的尾指针。然后第一个循环分别比较 prev，pcur对应结点的值，然后将小的插入到 newTail 处。该循环结束后还需要两个循环分别判断 list1,list2是否有剩余数据，有就将其尾插到 newTail 处，最后比较 list1, list2 第一个节点的大小，返回小的哪个头结点。
3. 需要注意的是开头需要判断两个链表是否有空链表，如果有一个为空，直接返回另一个链表头结点即可。

代码：

typedef struct ListNode SLTNode;struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{if(list1==NULL){return list2;}if(list2==NULL){return list1;}SLTNode* prev = list1;SLTNode* pcur = list2;SLTNode* newTail = NULL;//遍历比较两个链表while (prev && pcur){if (prev->val < pcur->val){if (newTail == NULL){newTail = prev;}else{newTail->next = prev;newTail = newTail->next;}prev = prev->next;}else{if (newTail == NULL){newTail = pcur;}else{newTail->next = pcur;newTail = newTail->next;}pcur = pcur->next;}}//一定会有个链表数据没有插入到新链表中while (prev){newTail->next = prev;newTail = newTail->next;prev = prev->next;}while (pcur){newTail->next = pcur;newTail = newTail->next;pcur = pcur->next;}//通过比较两个链表第一个值返回小的头结点return  list1->val < list2->val ? list1 : list2;
}

优化：

typedef struct ListNode ListNode;struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{if(list1==NULL){return list2;}if(list2==NULL){return list1;}ListNode* l1 = list1;ListNode* l2 = list2;ListNode*newHead,*newTail;//让newHead newTail指向同一块空间方便后续返回newHead = newTail = (ListNode*)malloc(sizeof(ListNode));while(l1 && l2){if(l1->val < l2->val){newTail->next=l1;newTail=newTail->next;l1=l1->next;}else{newTail->next=l2;newTail=newTail->next;l2=l2->next;}}while(l1){newTail->next=l1;newTail=newTail->next;l1=l1->next;}while(l2){newTail->next=l2;newTail=newTail->next;l2=l2->next;}ListNode*ret = newHead->next;free(newHead);return ret;
}

• 仅减少了一下分支结构，如果你有更简洁并且高效的代码欢迎评论区分享。

---

六、链表分割

链接：链表分割_牛客题霸_牛客网

思路：

1. 创建两个新链表，将小于x的结点存在一个链表中，大于等于x的结点存在另一个链表中。最后将两个新链表连接。
2. 依旧创建一个 pcur 指针遍历原链表
3. 
4. 分别尾插后：
5. 
6. 合并，最终结果：
7. 
8. 细节：记得将最后一结点的next指针置空

代码：

class Partition 
{
public:ListNode* partition(ListNode* pHead, int x) {// write code hereListNode*newHead1 = (ListNode*)malloc(sizeof(ListNode));ListNode*newHead2 = (ListNode*)malloc(sizeof(ListNode));//头尾指针开始都指向同一开辟的空间，方便后续返回和freeListNode*newTail1 = newHead1;ListNode*newTail2 = newHead2;ListNode*pcur = pHead;//分别尾插while(pcur){if(pcur->val < x){newTail1->next=pcur;newTail1=newTail1->next;}else {newTail2->next=pcur;newTail2=newTail2->next;}pcur=pcur->next;}//尾结点置空newTail2->next=NULL;//连接newTail1->next=newHead2->next;ListNode*ret = newHead1->next;free(newHead1);free(newHead2);newHead1=newHead2=NULL;return ret;}
};

---

七、链表的回文结构

链接：链表的回文结构_牛客题霸_牛客网

思路：

1. 局限解法：因为这题保证了链表长度小于900，那么我们可以创建一个900元素的数组保存链表的每一个结点的值，然后在数组中判断是否是回文结构，数组判断回文相对来说就简单很多，头尾往中间两两比较即可。缺点：如果相同一道题，不保证链表长度，并且空间复杂度为O(1)，那么这个方法就不行。
2. 通用解法：第一步---找到中间结点，第二步---逆置后半段链表，第三步---两两比较。
3. 我们实现通用解法：
4. 该方法结合了前面两题的解法：1.找中间结点，2.逆置链表
5. 
6. 
7. 细节：反转右半段链表时，依旧使用三指针法，需要注意的是mid结点的next指针指向为NULL
8. 

代码：

class PalindromeList {
public://找中间结点ListNode* findMidNode(ListNode* A){ListNode*fast = A;ListNode*slow = A;while(fast && fast->next){fast=fast->next->next;slow=slow->next;}return slow;}//逆置链表ListNode* reverseList(ListNode* mid){ListNode*n1, *n2;n1=NULL, n2=mid;while(n2){ListNode*n3=n2->next;n2->next=n1;n1=n2;n2=n3;}return n1;}bool chkPalindrome(ListNode* A) {// write code here//1.找中间结点ListNode* mid = findMidNode(A);//2.将后半段链表逆置ListNode* right = reverseList(mid);//3.逐一对比ListNode*left = A;while(right){if(left->val != right->val){return false;}left=left->next;right=right->next;}return true;}
};

---

八、相交链表

链接：160. 相交链表 - 力扣（LeetCode）

思路：

1. 首先分别遍历两个链表，计算它们的链表大小 sizeA和sizeB，然后根据大小创建两个指针 longList和shortList 分别指向长链表和短链表。
2. 我们先让长链表走 |sizeA-sizeB| 步，这样就可以保证两链表剩余长度一致，就可以同时遍历两个链表并且判断相交点在何处。
3. 这题主要难在理解上，两个链表相交，那么相交以后的链表长度肯定是一样长的，因为是单链表，只有一个next指针，不可能相交后再分叉。因此遍历两个链表前应该保证两个链表长度一致。

代码：

typedef struct ListNode ListNode;struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{int sizeA = 0;int sizeB = 0;ListNode*l1,*l2;l1 = headA;l2 = headB;//计算链表A的大小while(l1){++sizeA;l1=l1->next;}//计算链表B的大小while(l2){++sizeB;l2=l2->next;}//区分长短链表ListNode* longList = headA;ListNode* shortList = headB;if(sizeB>sizeA){longList = headB;shortList = headA;}int gap = abs(sizeA-sizeB);//让长的链表先走到与短链表一样长的位置while(gap--){longList=longList->next;}//同时遍历两个链表找出相交节点while(shortList && longList){if(shortList==longList){return shortList;}shortList=shortList->next;longList=longList->next;}return NULL;
}

---

九、环形链表

链接：141. 环形链表 - 力扣（LeetCode）

思路：

1. 快慢指针法。
2. 这题可以使用快慢指针快速解决，因为假如存在环形结构，两指针都进入环内，快指针 fast 的速度是慢指针 slow 的两倍，那么快指针一定会在环内追上慢指针。
3. 只要他俩相遇，就说明有环。

代码：

typedef struct ListNode ListNode;bool hasCycle(struct ListNode *head) 
{//快慢指针法ListNode*fast=head;ListNode*slow=head;while(fast && fast->next){fast=fast->next->next;slow=slow->next;if(fast==slow){return true;}}return false;
}

---

十、环形链表||

链接：142. 环形链表 II - 力扣（LeetCode）

思路：

1. 这题是在上一题的基础上要返回入环的第一个节点。
2. 这是一道经典的 Floyd's Cycle-Finding Algorithm（也称为“龟兔赛跑”算法）
3. 方法：依旧快慢指针找到它们第一次相遇的节点，然后保持其中一个指针不动，将另外一个指针回归到链表的头节点处。然后改变它们的速度每次都只走一步，同时开始移动，直到它们再次相遇，第二次相遇的节点就是入环的第一个节点。
4. 原理：
5. 

代码：

typedef struct ListNode ListNode;struct ListNode *detectCycle(struct ListNode *head) 
{ListNode*slow=head;ListNode*fast=head;//找相遇点，找到返回并重设slow位置while(fast && fast->next){slow=slow->next;fast=fast->next->next;if(fast==slow){slow=head;break;}}//找第二次相遇点while(fast && fast->next){if(fast==slow){return slow;}slow=slow->next;fast=fast->next;}return NULL;
}

---

十一、随机链表的赋值

链接：138. 随机链表的复制 - 力扣（LeetCode）

思路：

1. 这题讲的是“深拷贝”，即新链表的节点与原链表只是值和random指向关系一样，新链表的节点都是 malloc 开辟出来的。
2. 第一步，我们需要得到与原链表值相同的节点，而且数量也需要一致，先不管 random 指针。方法：我们单独创建一个方法 AddNode 创建新的节点，另外还有一个方法 BuyNode 用来申请新节点。在 AddNode 方法中，我们创建一个 pcur 指针用来遍历原链表，遍历的同时申请新节点。为了实现边遍历边拷贝，将新节点连接到原链表上：
3. 
4. 
5. 以上就是第一步，在原链表的基础上拷贝出新节点，此时新节点都连接在原链表上。
6. 第二步，为新节点连接 random 指针，我们以上面新节点 13 为例，它的 random 指针因该指向 7 的，我们使用两个指针遍历，一个指针 pcur 遍历原节点，一个 copy 遍历新节点，同步遍历，也就是说 pcur 指向是什么，copy 指向的就是 pcur 节点的复制节点，那么对于 13 来说，代码 copy->random = pcur->random->next ，pcur->random->next 刚好就是 7 的 next 节点，也就是新节点 7。这样就连接好了新节点 13 的random指针了。
7. 下图紫色线条表示 random 指针指向
8. 
9. 第三步，也就是最后一步，断开新节点与原节点的连接，使新节点之间相连。题目中没有要求恢复原链表之间的连接，因此不用管原链表了。断开连接方法：pucr 指针照样遍历原节点，定义 newHead 和 newTail 指针，它们首先指向新节点的头节点，然后循环，先让 pcur 走到下一个原节点，然后修改 newTial 的next指针连接，newTail->next=pcur->next。然后 newTail 往前走，pcur 继续走到下一个原节点。循环结束的条件就是 pcur->next->next == NULL。
10. 
11. 这样新链表就拷贝成功了。

代码：

typedef struct Node Node;//申请新节点
Node* BuyNode(int x)
{Node* newnode = (Node*)malloc(sizeof(Node));newnode->val=x;newnode->next=newnode->random=NULL;return newnode;
}//拷贝新节点
void AddNode(Node* head)
{Node*pcur = head;while(pcur){Node*Next = pcur->next;Node*newnode = BuyNode(pcur->val);pcur->next = newnode;newnode->next = Next;pcur = Next;}
}struct Node* copyRandomList(struct Node* head) 
{if(head==NULL){return NULL;}//1.在原链表上复制新链表AddNode(head);//2.根据原链表为新链表的random指针链接Node*pcur = head;while(pcur){Node*copy = pcur->next;if(pcur->random != NULL){copy->random = pcur->random->next;}pcur=copy->next;}//3.断开连接 pcur = head;Node*newHead,*newTail;newHead = newTail = pcur->next;while(pcur->next->next){pcur=pcur->next->next;newTail->next = pcur->next;newTail = pcur->next;}return newHead;
}