记录生活中的点点滴滴

0%

反转链表

最近有在刷leetcode开始先刷了一些简单的遇到了一个经常出现的知识点就是反转链表

以前我只晓得用头插法可以解决现在发现好像还有不少方法感觉这个知识点还是蛮重要的所以记录一下

这篇博客的主要内容有

  • 头插法反转链表
  • 遍历改变指针法反转链表
  • 递归法反转链表
  • 递归法按要求反转链表

头插法

首先也是最基本的一个方法就是使用头插法也就是先新建一个链表节点然后遍历所给链表把链表中的每一个节点头插到那个链表节点中去

注意我们新建的那个链表节点最好是无意义的一个头指针节点这样便于我们后续头插最后返回这个节点的next即可

1
2
3
4
5
6
7
8
9
10
11
12
13
//头插法解决
public ListNode reverseList(ListNode head) {
//约定新的头结点为-1
ListNode first = new ListNode(-1);
while(head!=null){
ListNode newNode = new ListNode(head.val);
//头插newNode节点
newNode.next = first.next;
first.next = newNode;
head = head.next;
}
return first.next;
}

不算难理解关键就是头结点最好是无意义的这样便于我们后续头插然后头插的逻辑示意图就像上面所示

遍历改变指针法

这个方法的意思就是遍历这个链表然后改变相邻的两节点的指针指向即可

我们先不管别的先动一下脑袋想一下

首先呢一个指针肯定是不够的我们需要两个指针prev``curr改变节点指针指向之后还要将两个指针前移继续下一个这样的操作

于是就产生了这样一个问题下移的时候curr怎样指向 本来curr的下一个节点

所以这种情况下肯定需要在更改指针前有一个指针指向curr下一个节点这个其实就像交换两个数需要有一个temp变量保存一下其中一个值

其实就是这样的示意图

关键是怎样去改变指针呢不难的

curr.next = prev

然后 prev和curr 都再往前进一步即可

这是中间的共性我们还要考虑边界情况也就是

prev为空curr执行第一个

curr为空prev指向最后一个的时候

第一种情况执行 curr.next=prev 其实没毛病因为本来反转后第一节点的next域就得是空

第二种情况也好办这其实就是循环退出的条件curr从本来执行第一个节点往下遍历迭代如果变为空的时候那么说明链表遍历完成了就是退出循环了不过记得返回的节点要是prev它才是原本最后一个节点也就是反转后的头结点

所以代码如下

1
2
3
4
5
6
7
8
9
10
11
12
//迭代改变指针法
public ListNode reverseList(ListNode head) {
ListNode curr = head;
ListNode prev = null;
while(curr!=null){
ListNode temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
return prev;
}

递归法

递归法反转链表以前还没有想到今天也长见识了

我先说说我今天才发现我今天之前在递归上的一个很大的误区

遇见递归我总是想无限套娃也就是把自己代入进去看看下一个递归下一个然后看看是啥情况这可太错误沙比了

对于递归算法最重要的就是明确递归函数的含义用这个功能在递归的代码中去解决遇到的问题让它自己递归就行了只要我们已经明确这个递归函数的含义还有就是base case也就是出口

好的下面来看看怎样用递归算法解决链表的反转

我们先明确这个函数的意义就是输入一个节点 **head将以 head **为起点的链表反转并返回反转之后的头结点

比如我们想反转如下链表首先已经定义了这个函数 reverse(LinkList head)

我们把 head.next 这个节点传入到我们这个反转函数reverse会返回啥子

就是这样我们这个函数的关键就是怎样将这个head和返回的last这两个链表按要求连起来即可

其实就是 head.next.next = head 然后 head.next=null 返回last节点即可

就是这么简单不过还有base case需要注意

也就是 if(head.next==null) return head;

就是最后一个节点时就它一个节点不用干啥直接返回这个head即可

下面就是代码

1
2
3
4
5
6
7
8
//递归解决
public ListNode reverseList(ListNode head) {
if(head==null || head.next==null) return head;
ListNode last = reverseList(head.next);
head.next.next = head;
head.next = null;
return last;
}

对于直接传入的head为空null时直接返回head也就是null这种情况也要考虑在内

递归反转链表前N个节点

这次我们实现一个这样的函数

1
2
// 将链表的前 n 个节点反转n <= 链表长度
ListNode reverseN(ListNode head, int n)

比如说对于下图链表执行 reverseN(head, 3)

其实这个解决方法和前面递归法反转整个链表差不多无非需要一个指针记录第n+1个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ListNode successor = null; // 后驱节点

// 反转以 head 为起点的 n 个节点返回新的头结点
ListNode reverseN(ListNode head, int n) {
if (n == 1) {
// 记录第 n + 1 个节点
successor = head.next;
return head;
}
// 以 head.next 为起点需要反转前 n - 1 个节点
ListNode last = reverseN(head.next, n - 1);

head.next.next = head;
// 让反转之后的 head 节点和后面的节点连起来
head.next = successor;
return last;
}

递归反转链表的一部分

给一个索引区间 [m,n]索引从 1 开始仅仅反转区间中的链表元素

1
ListNode reverseBetween(ListNode head, int m, int n)

首先如果m=1其实就相当于我们反转前n个节点的用上面的函数即可

如果 m != 1 怎么办如果我们把 head 的索引视为 1那么我们是想从第 m 个元素开始反转对吧如果把 head.next 的索引视为 1 呢那么相对于 head.next反转的区间应该是从第 m - 1 个元素开始的那么对于 head.next.next

区别于迭代思想这就是递归思想所以我们可以完成代码

1
2
3
4
5
6
7
8
9
ListNode reverseBetween(ListNode head, int m, int n) {
// base case
if (m == 1) {
return reverseN(head, n);
}
// 前进到反转的起点触发 base case
head.next = reverseBetween(head.next, m - 1, n - 1);
return head;
}

递归总结

递归的思想相对迭代思想稍微有点难以理解处理的技巧是不要跳进递归而是利用明确的定义来实现算法逻辑

处理看起来比较困难的问题可以尝试化整为零把一些简单的解法进行修改解决困难的问题

值得一提的是递归操作链表并不高效和迭代解法相比虽然时间复杂度都是 O(N)但是迭代解法的空间复杂度是 O(1)而递归解法需要堆栈空间复杂度是 O(N)所以递归操作链表可以作为对递归算法的练习或者拿去和小伙伴装逼但是考虑效率的话还是使用迭代算法更好

参考博客

labuladong–递归反转链表的一部分

LeetCode 例题精讲 | 01 反转链表如何轻松重构链表