题解 | #反转链表#

链表的位置域需要有一个比较深的理解，定义一个临时变量指向头结点，当临时变量向next移动，头结点不变，临时变量的next被赋值，头结点的next也跟着被赋值了

• 方法1，利用栈先进后出的特性，先把节点的next域赋null，压入栈中，这样每个元素都是单一元素，出栈时，将第一个元素赋给头结点，此位置不能改变，所以定义一个临时变量，向后移动，每弹出一个元素，找到当前指针指向的最后一个位置（next=null）即可。

import java.util.*;
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
       ListNode node = null;
       Stack<ListNode> stack = new Stack<>();
        while(head!=null){
            ListNode temp = head.next;
            head.next = null;
            stack.push(head);
            head = temp;
        }
        if(stack.empty())return null;
        node = stack.pop();
        ListNode cur = node;
        while(!stack.empty()){
            ListNode temp = stack.pop();
            while(true){
                while(cur.next != null){
                    cur = cur.next;
                }
                cur.next = temp;
                break;
            }
        }
        return node;
    }
}

• 方法二：将链表从头到尾遍历，每次遍历的数都放在新的头结点，将头结点的next域指向原来的头结点

import java.util.*;
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
       ListNode node = null;
       
       while(head!=null){
           ListNode temp = head.next;

           if(node==null){
               head.next = null;
               node = head;
           }
           
           else{
               ListNode n1 = node;
               head.next = null;
               node = head;
               node.next = n1;
           }
           
           head = temp;
       }
        
       return node;
    }
}

• 还是要深入理解链表，这次使用递归算法,当链表长达大于1时，递归获取next为null的节点，此节点为最后一个，然后将此节点插入到头结点最前面。

• 例如 1,2,3,null
• round1:链表长度大于1，遍历2,3,null，等待结果
• round2:链表长度仍大于1，遍历3,null，等待结果
• round3：链表长度等于1，返回3
• 回到round2:遍历3,null的结果是3,null,将3,null插入到2,3,null的前面，将2的next置为null，3的next置为2，返回3,2,null
• 回到round1：遍历2,3,null的结果是3,2,null，将3,2,null插入到1,2,3,null的最前面，将1的next置为null，2，next置为1，返回3,2,1,null

import java.util.*;
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head == null || head.next == null)
            return head;
        
        ListNode next = head.next;
        
        ListNode node = ReverseList(next);
        
        head.next = null;
        ListNode temp = node;
        while(temp.next!=null){temp = temp.next;}
        temp.next = head;
        
        return node;
    }
}