[算法]——链表（三）

目录

​编辑

一、前言

二、正文

1.重排链表

1.1 题目解析

1.2 算法原理

1.3 具体代码

2.K个一组翻转链表

2.1 题目解析

2.2 算法原理

2.3 具体代码

三、结语

一、前言

        本文将继续为大家带来链表的学习！！！

二、正文

1.重排链表

1. 重排链表 - [力扣]

1.1 题目解析

        本题要求要求我们对所给链表进行重排，那么观察题目所给示例，我们会发现所谓重排后的链表，就是先头结点，尾结点，然后头结点的下一个节点，尾结点的前一个节点……y依次类推，直至链表所有的元素都被插入。

1.2 算法原理

         那么本题的原理依旧是模拟的思路，那么该如何模拟呢？

具体的步骤如下:

1.找到链表的中间节点——利用快慢双指针

2.根据快慢双指针将链表分为两部分，对slow指针后面的部分进行逆序（使用头插法），其目的是为了该部分插入的顺序与我们模拟的插入相同

3.合并两个链表——利用双指针

1.3 具体代码

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: void reorderList(ListNode* head) { if(head->next==nullptr) return ; ListNode* ret=new ListNode; ListNode* back=new ListNode; //找到链表中的中间节点 ListNode *slow=head,*fast=head->next; while(fast->next && fast->next->next) { slow=slow->next; fast=fast->next->next; } //head-slow（前） slow->next-tail（后） //对后面的链表进行逆序 ListNode *cur=slow->next; while(cur) { ListNode* next=cur->next; if(back->next==nullptr) { back->next=cur; cur->next=nullptr; //不处理会导致死循环 } else { cur->next=back->next; back->next=cur; } cur=next; } //合并两个链表 slow->next=nullptr; ListNode *cur1=head,*cur2=back->next,*cur3=ret; while(cur1 && cur2) { cur3->next=cur1; cur1=cur1->next;//二三行不能颠倒， cur3=cur3->next; cur3->next=cur2; cur2=cur2->next; cur3=cur3->next; } while(cur2) { cur3->next=cur2; cur2=cur2->next; } head=ret->next; } };

2.K个一组翻转链表

2.1 题目解析

        本题与我们之前讲过的一题类似，不知道小伙伴们还记不记得“两两交换链表中的节点”那道题，那道题要求我们对来链表中的两两节点进行交换，而本题则是提升了一点难度，交换的节点个数为k个，对于不足k个节点则不用进行交换

2.2 算法原理

        本题的算法思路依旧是模拟，即模拟题目交换节点的过程

具体步骤如下：

1.求出需要逆序的组数n

2.重复n次：长度为k的链表逆序

3.把不需要翻转的链表接在最后一次翻转的节点之后



注：这里要注意的一点在每次逆序结束之后，我们都要将prev节点重新调整位置至下一次要逆序的第一个节点的前一个，即我们本次逆序链表的首个插入节点。

2.3 具体代码

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* reverseKGroup(ListNode* head, int k) { //1.求出需要逆序的组数 ListNode* cur = head; int n = 0; while (cur) { n++; cur = cur->next; } n/=k; //2.重复n次：长度为k的链表逆序 ListNode* newhead = new ListNode(0); ListNode* prev = newhead; cur = head; for(int i=0;i < n;++i) { ListNode* tmp=cur; for(int j=0;j<k;j++) { ListNode* next = cur->next; cur->next = prev->next; prev->next = cur; cur = next; } prev=tmp; } //把不需要翻转的接上 prev->next = cur; return newhead->next; } };

三、结语

         到此为止，本文关于链表（三）内容到此结束了，如有不足之处，欢迎小伙伴们指出呀！

         关注我 _麦麦_分享更多干货：_麦麦_-ZEEKLOG博客

         大家的「关注❤️ + 点赞👍 + 收藏⭐」就是我创作的最大动力！谢谢大家的支持，我们下期见！

        欢迎大家参观我的算法专栏：

麦麦的算法专栏https://blog.ZEEKLOG.net/m0_73953114/category_12866812.html