5

Leetcode 25 Reverse Nodes in k-Group 题解分析-再解分析

 1 year ago
source link: https://nicksxs.me/2024/01/21/Leetcode-25-Reverse-Nodes-in-k-Group-%E9%A2%98%E8%A7%A3%E5%88%86%E6%9E%90/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

Leetcode 25 Reverse Nodes in k-Group 题解分析-再解分析

上一次主要是给了一个解题方案，没有具体讲解，这次又做到了就来看下几种方案，链表转置一直是我比较疑惑的问题，特别是边界处理，而这个问题要把难度加大了
我先讲一下我一开始的思路和解题方法，首先就是写一个转置方法，就处理 k 个一组的内部转置，然后外部循环处理分组以及前后连接等问题，但是这里就涉及到一个问题，就是前后连接的话对于整个链表头，也就是第一个 k 元素组来说，头是个空的，就需要额外处理，一开始就是用判空做额外处理，然后在前后连接的时候也有一些困扰，看了自己的代码库发现其实之前也做过，而且发现这个思路跟以前做的还是一样的，只不过在处理 k 个元素内部的转置的时候有了点差异

一开始的思路是这样的，想了下其实还是比较有问题，从处理难度上来说，在 k 组内处理的时候一开始 A 节点会是悬空的，然后得处理到组内最后一个元素的时候再接上，逻辑会更复杂，而另一种思路就是直接把 A 先挪到 C 后面，这样每次只需要移动一个，可能思路上会更清晰一点

也就是这样的，这种方案就是之前发过的题解代码，上一篇

而最后这种则代码会简单一些，但是需要一定的理解成本，比较重要的一点是我们加了个虚拟的头结点，第一步会先获取下链表的总长度，然后在内循环里处理转置，重点就是分四步，
也就是图里的，第一步先把 cur 的下一个节点设置成 next 的 next 节点，这里就是图里 A 连接到 C，第二步是把 next 的 next 节点设置成虚拟头的 next节点，第三步是把 pre 的next 节点设置成 next，第四步是 next 往后移动

cur.next = next.next;
next.next = pre.next;
pre.next = next;
next = cur.next;

在备注下代码


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK