java 剑指offer之[数据结构 简单]JZ15 反转链表

题目的链接在这里：https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca

• 题目大意
• 一、示意图
• 二、解题思路
• • 递归
  • 暴力栈
  • 正常情况

递归和暴力栈 正常情况

代码如下：

public class Solution {
    public ListNode ReverseList(ListNode head) {
        //反转链表
        //递归的方法
        if(head==null)
            return null;
            //还需要判断一个
        if(head.next==null)
            return head;
        //不然的话
        //这里要断一下
        ListNode listNode = ReverseList(head.next);
        ListNode finalNode=listNode;
        head.next=null;
        while (listNode.next!=null){
            listNode=listNode.next;
        }
        //直到指向ListNode的下一个是null 
        listNode.next=head;
        return finalNode;
        
    }
}

代码如下：

import java.util.*;
public class Solution {
       public ListNode ReverseList(ListNode head) {
        //暴力手段
        //使用一个栈来存储当前的节点值
        Stack stack=new Stack<>();
        if(head==null)
            return null;
        if(head.next==null)
            return head;
        while (head!=null){
            stack.add(head.val);
            head=head.next;
        }
        //然后通过创建来实现
        ListNode listNode=new ListNode(stack.pop());
        ListNode finalNode=listNode;
        while (!stack.isEmpty()){
            ListNode temp=new ListNode(stack.pop());
            //先把这个的下一个指向temp
            listNode.next=temp;
            //然后再自己指向这个
            listNode=temp;
        }
        return finalNode;

    }
}

代码如下：

import java.util.*;
public class Solution {
          public ListNode ReverseList(ListNode head) {
        //最正常的解法
        //先进行边界判断
        if(head==null||head.next==null)
            return head;
        ListNode pre=null;
        ListNode next;
        
        while (head!=null){
            //找到下一个位置
            next=head.next;
            //向后面开始转 
            head.next=pre;
            //然后pre始终指向需要更新的最右边的节点
            pre=head;
            //head指向下一个需要更新的节点
            head=next;
        }
        return pre;
    }
}