赞
踩
定义一个单链表
因为我这里待会测试的时候需要自定义测试用例,所以就生成了get和set方法
- public class ListNode {
- public int val;
- public ListNode next;
-
- public int getVal() {
- return val;
- }
-
- public void setVal(int val) {
- this.val = val;
- }
-
- public ListNode getNext() {
- return next;
- }
-
- public void setNext(ListNode next) {
- this.next = next;
- }
-
- public ListNode() {
- }
-
- public ListNode(int val) {
- this.val = val;
- }
-
- public ListNode(int val, ListNode next) {
- this.val = val;
- this.next = next;
- }
- }
反转链表是一道十分常见的面试题,我们都应该需要掌握的它的解题办法
解决思路如下:
假设这个链表是1-->2-->3-->4-->5-->null,我们需要返回的链表就是5-->4-->3-->2-->1-->null
根据上面单链表的定义我们可以知道,每个节点都只保存了它的下一个节点的指针next,而没有保存它前一个节点的指针,当链表进行反转后,每个节点的下一个节点就变成了它原来的前一个节点,比如原先是1-->2-->3-->4-->5-->null,反转后就变成了5-->4-->3-->2-->1-->null,所以我们需要提前保存每个节点的前一个节点,然后在我们遍历链表的过程中,需要将当前节点的next 指针改为指向它的前一个节点,一定要记得!!我们修改next指针之前必须先保存原先节点的后一个节点,不然修改next指针后原先节点它的后一个节点就访问不到了,最后返回新的头节点。
初始状态:
第一轮反转
第二轮反转
接下来的都是在重复相同的步骤,直到完成!
递归可能有点不太好理解,直接看代码就能看懂了。在这里不太好描述
- /**
- * @author lqkj
- * @data 2022/11/28 16:48
- * 例如: 1 -> 2 -> 3 -> 4 -> 5 -> null
- * 通过变化以后,变成 5 -> 4 -> 3 -> 2 -> 1 -> null
- * 给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
- */
- public class Reversal {
-
- //第一种解决办法,常见的直接反转
- public ListNode reverseList(ListNode head){
- ListNode prev = null; //表示当前节点的前一个节点,初始值为null
- ListNode temp = head; //表示当前节点,初始值为head
- ListNode next; //表示当前节点的下一个节点
- while(temp != null){
- //先提前保存当前节点的下一个节点
- next = temp.next;
- //将当前节点的next指针指向当前节点的下一个节点
- temp.next = prev;
- //更新prev,将temp的值赋给prev
- prev = temp;
- //更新temp,将next赋给temp
- temp = next;
- }
- return prev; //退出循环时temp为null,那么temp的前一个节点prev为新的头结点
- }
- //第二种方法,使用递归
- public ListNode reverseList2(ListNode head){
- //递归终止的条件是当前为空,或者下一个节点为空
- if(head == null || head.next == null){
- return head;
- }
- //这里的pre就是最后一个节点
- ListNode pre = reverseList2(head.next);
- //如果链表是1->2->3->4->5,难么pre此时就是5
- //head是4,head的下一个就是5,下下个就是null
- //所以head.next.next 就是 5->4
- head.next.next = head;
- //防止链表形成循环,需要将head.next 设置为null
- head.next = null;
- //每层都返回pre,也就是最后一个节点
- return pre;
- }
- public class ReversalTest {
-
- //输出函数
- private void print(ListNode head){
- while(head != null){
- System.out.println(head.getVal() + " " + head.getClass().getName());
- head = head.next;
- }
- }
-
- //封装链表赋值函数
- public ArrayList<ListNode> arrayList(int n){
- ArrayList<ListNode> list = new ArrayList<>();
- for(int i = 1 ; i <= n ; ++i){
- ListNode node = new ListNode();
- node.setVal(i);
- list.add(node);
- if(i != 1){
- list.get(i-2).setNext(list.get(i-1));
- }
- if( i == n){
- list.get(i-1).setNext(null);
- }
- }
- return list;
- }
-
-
- @Test
- public void testList(){
- int n = 5;
- ArrayList<ListNode> list = arrayList(n);
-
- ListNode head = list.get(0);
-
- print(head);
- System.out.println("-----------------------------");
-
- ListNode reve = new Reversal().reverseList(head);
- ListNode reve2 = new Reversal().reverseList2(head);
- print(reve);
- print(reve2);
- }
-
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。