链表翻转三题 BM1 BM2 BM3
输入:指向第一个节点的指针head
准备工作
定义链表结构,输出链表,初始化链表
struct ListNode{ explicit ListNode(int n):val(n){} int val; struct ListNode* next= nullptr; }; ListNode* List_init(int num){ auto *head = new ListNode(1); ListNode *p = head; for (int i=2;i<=num;i++) { auto q=new ListNode(i); p->next=q; p=q; } return head; } void showoff(ListNode* head){ auto p=head; while (p){ cout<<p->val<<" "; p=p->next; } cout<<endl; }
BM1 翻转链表
要求:翻转整个链表,输出指向翻转后的第一个节点指针
思路:遍历链表,头插生成新链表
ListNode* reverse_list(ListNode* head){ if (head== nullptr||head->next== nullptr){ return head; } auto new_head = new ListNode(0); auto p = head; while (p){ auto new_node = new ListNode(p->val); new_node->next=new_head->next; new_head->next=new_node; p=p->next; } return new_head->next; }
BM2 翻转链表指定区间
BM3 分组翻转链表
两题一起考虑
封装一个函数,输入一个一对指针,分别指向待翻转链表分组第一个节点前一个节点(即前一组末或理解为加装头节点)与本组末节点,输出一对指针,分别指向翻转后的组头与组末
pair<ListNode*, ListNode*> reverseBetween(ListNode* head, ListNode* end){ // 翻转head->next到end if (head== nullptr||head->next== nullptr){ return {head,end}; } auto new_head = new ListNode(0); auto p = head->next; auto new_end = new ListNode(p->val); new_head->next=new_end; p=p->next; while (p!=end->next){ auto new_node = new ListNode(p->val); new_node->next=new_head->next; new_head->next=new_node; p=p->next; } return {new_head->next,new_end}; }
利用此函数完成两题,均加装头节点
ListNode* reverseBetween(ListNode* head,int m,int n){ if (m>n||head== nullptr||head->next== nullptr){ return head; } auto newhead = new ListNode(0); newhead->next=head; auto verse_head = newhead; auto verse_end= head; while (--m){ verse_head=verse_head->next; } // cout<<verse_head->val<<endl; while (--n){ verse_end=verse_end->next; } // cout<<verse_end->val<<endl; auto (p)= reverseBetween(verse_head,verse_end); // showoff(p.first); verse_head->next=p.first; p.second->next=verse_end->next; return newhead->next; }
ListNode* reverseKGroup(ListNode* head, int k) //按分组翻转 { auto newhead = new ListNode(0); newhead->next=head; auto p=newhead,q=newhead; //p指向翻转组前组末,q指向本组末 while (true){ int count=k; while (count--) { q=q->next; if (q== nullptr){ return newhead->next; } } auto r=reverseBetween(p,q); p->next=r.first; r.second->next=q->next; q=r.second; p=q; } }