LeetCode刷题笔记-数据结构-day13

柔光的暖阳◎ 2023-10-01 16:52 16阅读 0赞

#### 文章目录 ####

*  LeetCode刷题笔记-数据结构-day13
 *   *  25. K 个一组翻转链表
     *   *  1.题目描述
         *  2.解题思路
         *  3.代码
     *  143. 重排链表
     *   *  1.题目描述
         *  2.解题思路
         *  3.代码

## LeetCode刷题笔记-数据结构-day13 ##

### 25. K 个一组翻转链表 ###

#### 1.题目描述 ####

> 原题链接：[25. K 个一组翻转链表][25. K]

![image-20220127094934715][]

![image-20220127094958211][]

#### 2.解题思路 ####

我们可以考虑分这几步：

1.  增加虚拟头节点，方便后续操作
2.  判断接下来的一段个数是否大于等于k
3.  如果满足2，将这段进行反序
4.  将倒序后的尾节点指向下一段的头节点
5.  将p指针的next更新为倒序后的头部
6.  更新p为倒序后的尾部，进行下一个反序操作

#### 3.代码 ####

class Solution {
        
    public:
        ListNode* reverseKGroup(ListNode* head, int k) {
        
            
                ListNode* dummy=new ListNode(-1);
                dummy->next=head;
                for(auto p=dummy;;){
        
                    auto t=p;
                    //2
                    for(int i=0;i<k&&t;i++) t=t->next;
                    if(!t) break;
                    auto a=p->next,b=a->next;
                    //3
                    for(int i=0;i<k-1;i++){
        
                        auto c=b->next;
                        b->next=a;
                        a=b,b=c;
                    }
                    auto c=p->next;
                    //4
                    c->next=b;
                    //5
                    p->next=a;
                    //6
                    p=c;
                }
                return dummy->next;
        }
    };

### 143. 重排链表 ###

#### 1.题目描述 ####

> 原题链接：[143. 重排链表][143.]

![image-20220127103344032][]

![image-20220127103401156][]

#### 2.解题思路 ####

根据题目的意思我们可以用以下方法：

假设初始的链表是 `L1→L2→L3→…→LnL1→L2→L3→…→Ln`。

1.  将后半段的指针都反向，变成：`L1→L2→L3→…→L⌈n/2⌉←L⌈n/2⌉+1←…←Ln`
2.  用两个指针分别从1和n开始往中间扫描，将后半段交替插入到前半段，变成：`L1→Ln→L2→Ln−1→…`

模拟，这里分几步：

1.  先求出链表的总长度
2.  然后将后半段链表反向
3.  最后将后半段和前半段一起遍历，融入前半段

#### 3.代码 ####

class Solution {
        
    public:
        void reorderList(ListNode* head) {
        
            int n=0;
            //求出链表总长度
            for(auto t=head;t;t=t->next) n++;
            if(n<=2) return;
            auto later=head;
            //找出中心点
            for(int i=0;i+1<(n+1)/2;i++) later=later->next;
            auto a=later,b=a->next;
            //将后半段翻转
            while(b){
        
                auto c=b->next;
                b->next=a;
                a=b,b=c;
            }
            later->next=nullptr;
            //将后半段交替插入到前半段
            while(head&&head!=a){
        
                b=a->next;
                a->next=head->next;
                head->next=a;
                head=head->next->next;
                a=b;
            }
    
        }
    };

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBATEwuTEVCUk9O_size_20_color_FFFFFF_t_70_g_se_x_16]

[25. K]: https://leetcode-cn.com/problems/reverse-nodes-in-k-group/
[image-20220127094934715]: https://img-blog.csdnimg.cn/img_convert/0c57b425fb7aeef0f15d8ed3c1bdabb0.png
[image-20220127094958211]: https://img-blog.csdnimg.cn/img_convert/0d5d51adeb022c5311165c99ddb3a5b8.png
[143.]: https://leetcode-cn.com/problems/reorder-list/
[image-20220127103344032]: https://img-blog.csdnimg.cn/img_convert/6d4e2bcd3af1788f5cc8b2449a1949a7.png
[image-20220127103401156]: https://img-blog.csdnimg.cn/img_convert/2d0bfb43f19439d72c38b748c473387d.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBATEwuTEVCUk9O_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/6824e777ad80419b9b4d90ce502a8e27.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBATEwuTEVCUk9O,size_20,color_FFFFFF,t_70,g_se,x_16