Java题目详解——LeetCode206.反转链表（包含三种解法，迭代，栈，递归）_java 链表反转 迭代

目录

题目链接：反转链表

一.题目要求

二.解题思路

1.使用迭代法

2.使用栈结构

3.使用递归思想

三.具体代码

1.使用迭代法

2.使用栈结构

3.使用递归思想

四.运行截图

1.使用迭代法

2.使用栈结构

​3.使用递归思想

---

题目链接：反转链表

一.题目要求

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

二.解题思路

1.使用迭代法

        首先，我们要逆置该链表，最先想到的肯定是需要循环遍历该链表。

ListNode cur=head;
while(cur!=null){
    cur=cur.next;
}

        然后在循环遍历的基础上，对结点进行逆置。

        如果我们想改变cur到下一个结点的引用，使其指向cur的前一个结点，那我们就要提前记录下cur的前一个结点（prev），从而改变cur的引用，成功后使cur和prev都向后移动。

        这时我们可以发现一个问题，在cur.next=prev时，cur的下一步引用就被改变了，是指向prev的，比如在这张图中，2逆置后就指向1，不再指向3，接下来的cur=cur.next不会使cur从2变到3，那我们如何使cur向后移动呢？

        我们可以新建一个结点（next）先指向cur.next，最后再使cur=next即可。

考虑头结点和尾结点的情况：

头结点成立：

 尾结点成立： 

 并且由此可见，我们最后返回的链表头结点应该是prev。

 如想了解链表（LinkedList）相关知识，请查阅：

LinkedList（链表）的介绍及自我实现

2.使用栈结构

        首先，我们要知道栈的结构特点是 "先进先出" ，如果想要逆序链表，那我们可以先将链表结点一个一个 "压栈" ，等所有结点都入栈后，再一个一个 "出栈" 即可，这样就实现了链表的逆序。

需要注意的是：

(1).本题要求返回的类型是ListNode类型，也就是头结点（start），所以需要我们新建一条链表，并且新建一个移动结点（tmp），由于我们需要进行tmp=tmp.next的解引用操作，所以我们新建的不能是空链表。

ListNode start=new ListNode(0,ListNode(0));
ListNode tmp=start;

(2).那么为什么一开始进入循环后就要使tmp.next=stack.pop()呢？为什么不能使tmp=stack.pop()？

这是为了和反转的是空链表的情况统一，所以将第一个结点（start）设置为工具结点，从（start.next）才开始操作，所以最后需要返回的是start.next。

while(!stack.isEmpty()){
    tmp.next=stack.pop();
    tmp=tmp.next;
}
return start;

(3).循环结束后要将tmp.next=null，也就是将尾结点的下一个设置为null，防止链表中出现环。

tmp.next=null;

3.使用递归思想

        首先我们要思考递归最后结束的条件是什么，第一种情况是链表是个空链表，即head==null；第二种情况就是head移动到尾结点，即head.next=null，这两种情况时返回head（经历递归函数的话会变为newHead），否则对下一个结点进行逆置操作。

if(head==null||head.next==null){
    return head;
}

        所以，调用递归函数的顺序是从head开始向后（调用时刷新逆序后的新结点newHead），那么进行逆序的顺序是从倒数第一个结点开始，依次向前进行结点的逆序操作。

ListNode newHead=reverseList(head.next);

具体的逆序操作是怎样的呢？ 

        我们可以记录下前驱结点（ListNode prev=head）和当前结点（ListNode cur=head.next），然后使当前结点指向前驱结点（cur.next=prev），然后一定要使前驱结点的指向为null（prev.next=null），否则逆置后的链表可能会产生环。

//记录前驱结点
ListNode prev=head;
//记录当前结点
ListNode cur=head.next;
//使当前结点指向前驱结点
cur.next=prev;
//使前驱结点的指向为空
prev.next=null;

三.具体代码

1.使用迭代法

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode cur=head;
        ListNode prev=null;
        while(cur!=null){
            ListNode next=cur.next;
            cur.next=prev;
            prev=cur;
            cur=next;
        }
        return prev;
    }
}

2.使用栈结构

class Solution {
    public ListNode reverseList(ListNode head) {
        Deque<ListNode> stack=new LinkedList<>();
        ListNode cur=head;
        while(cur!=null){
            ListNode e=cur;
            stack.push(e);
            cur=cur.next;
        }
        ListNode start=new ListNode(0,ListNode(0));
        ListNode tmp=start;
        while(!stack.isEmpty()){
            tmp.next=stack.pop();
            tmp=tmp.next;
        }
        tmp.next=null;
 
        return start;
    }
}

3.使用递归思想

class Solution {
    public ListNode reverseList(ListNode head) {
        //从后向前递归逆转
        //空链表 或 到达链表结尾 返回
        if(head==null||head.next==null){
            return head;
        }
        //逆转下一个结点
        ListNode newHead=reverseList(head.next);
        //记录前驱结点
        ListNode prev=head;
        //记录当前结点
        ListNode cur=head.next;
        //使当前结点指向前驱结点
        cur.next=prev;
        //使前驱结点的指向为空
        prev.next=null;
 
        return newHead;
    }
}

四.运行截图

1.使用迭代法

2.使用栈结构

 3.使用递归思想

 如有建议或想法，欢迎一起讨论学习~