网站建设客户源,网站需要条件,注册一个免费的网站,建设银行宁夏分行网站单链表的反转#xff08;面试常出#xff09;#xff1a;
单链表的反转#xff0c;可以通过很多种方法实现。包括迭代法#xff0c;递归法#xff0c; 迭代法#xff1a; 定义三个指针#xff1a;prev、current和next#xff0c;它们分别表示前一个节点、当前节点…单链表的反转面试常出
单链表的反转可以通过很多种方法实现。包括迭代法递归法 迭代法 定义三个指针prev、current和next它们分别表示前一个节点、当前节点和下一个节点。 初始化时prev为nullcurrent为头节点。 在循环中不断将current的next指针指向prev然后依次向后移动prev、current和next指针。 当next为空时说明已经到达链表末尾此时的prev指向就是反转后的头节点。 其实就像是先将第一个节点指向null就像最后一个节点它也是next null的然后一直这样子重复转一次就后退让下一个节点去转方向指向前面的。 public ListNode reverse(Node head) {Node prev null;Node current head;while (current ! null) {Node nextTemp current.next; // 暂存当前节点的下一个节点current.next prev; // 将当前节点指向前一个节点prev current; // 更新prev为当前节点current nextTemp; // 更新current为原先的下一个节点}return prev; // 返回反转后的头节点}// 补充一个力扣第92题加深理解让你把单链表部分元素反转其他部分不变
这里依旧可以使用迭代的方法就是要先通过遍历去找到反转开始的位置和结束的位置用辅助节点记录反转区间的前置节点和反转区间的尾节点。然后反转区间的链表反转即可反转后接上前面的部分。 public ListNode reverseBetween(ListNode head, int left, int right) {ListNode current head;ListNode prev null;for (int i 1; i left; i) {prev current;current current.next;}// 反转区间的前置节点ListNode tailPrev prev;// 反转区间的尾节点ListNode tail current;// 同样的迭代原理只是范围要自定义。for (int j left; j right; j) {ListNode newTemp current.next;current.next prev;prev current;current newTemp;}// 反转区间的头节点ListNode headReverse prev;tail.next current;if (tailPrev ! null) {tailPrev.next headReverse;return head;} else {return headReverse;}
}
递归法也是力扣第206题
递归的关键是看整体找出整体的大块东西。可以先写一个伪代码过一遍思路。你就写基础情况然后要的操作再看子问题递归调用放的位置即可。
**实操技巧**第一步先找到可以看作整体的就是原理一样的。去设计递归调用超级操作第二步去设计微操作去看一份整体的怎么实现即可。后面就去找到题目中的基础情况它相当于最里面的超级操作了也基本就是剩下一个的情况那种。
相关概念
1.首先先明确函数的意义还要原问题和子问题。在这里原问题是给整个链表反转子问题是给每一个字节进行反转。
2.基础情况也就是要找到结束的条件。就是当数据规模很小的时候能结束递归返回答案。
3.递归调用超级操作怎么搞定中间的递归操作。但是唉人脑进去递归出不来的。所以得完把递归的过程看成一个整体不要去想里面怎么运行的。
4.微操作。也就是操作的方法。
比如汉诺塔问题你有2个叠在一起的时候就是先把小的放中间大的放右边再把小的放大的上面。那这个时候假如他有一堆你就是把小的一堆给放到中间让最大的去到最右边垫底。然后小的一堆整体放到大的上面。而那一堆小的移动其实就是整个问题的子问题它其实就是可以用递归重复一个原理完成。
此题思路如下 // 定义输入一个单链表头结点将该链表反转返回新的头结点
ListNode reverse(ListNode head) {// 基础情况也就是结束的代码。// 链表为空或者只有一个节点时直接返回头节点即可。if (head null || head.next null) {return head;}// 递归调用超级操作ListNode last reverse(head.next);// 而其实当你写一个伪代码时候你也可以发现。下面的这个其实就是反转需要的的操作可以写一个伪代码微操作。具体操作方法 operate(head.next); head.next.next head;head.next null;return last;
}
