Leetcode刷题 206. 反转链表递归迭代两种方法实现

原创

一只胡说八道的猴子

修改于 2020-10-09 10:01:11

5360

文章被收录于专栏：Java系列学习与数据结构算法Java系列学习与数据结构算法

题目链接

**链接**：https://leetcode-cn.com/problems/reverse-linked-list/

题目描述

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL

输出: 5->4->3->2->1->NULL

进阶:

你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

预置代码

/\*\*

 \* Definition for singly-linked list.

 \* public class ListNode {

 \*     int val;

 \*     ListNode next;

 \*     ListNode(int x) { val = x; }

 \* }

 \*/

class Solution {

    public ListNode reverseList(ListNode head) {

         

    }

}

解题思路

方法一：递归实现

**未反转前**

**反转后**

**构造一个函数reverseList(ListNode head)进行链表反转**

    public ListNode reverseList(ListNode head) {

        /\*如果传入的节点等于null则之间返回head说明只有一个，无需反转\*/

        if (head==null){

            return  head;

        }

        /\*如果传入节点的下一个节点为null，说明递归结束，开始进行返回节点\*/

        else if (head.next==null){

            return head;

        }

        /\*进行递归循环，newHead保存的是最后一个节点的位置\*/

        ListNode newHead = reverseList(head.next);

        /\*传入的head节点的后继节点的next指向head，实现反转\*/

        head.next.next=head;

        /\*head的next=null\*/

        head.next=null;

        return  newHead;

    }

**精解后的代码**

public ListNode reverseList(ListNode head) {

        if (head==null||head.next==null){

            return  head;

        }

        ListNode newHead = reverseList(head.next);

        head.next.next=head;

        head.next=null;

        return  newHead;

    }

大家如果觉得光看代码难以理解可以通过边画图边读代码的方式来进行理解，这样我感觉学起来更容易

方法二：迭代

这个理解起来应该比递归要容易的多

public ListNode reverseList(ListNode head) {

        /\*如果head==null或则head.next==null，

        即说明只有一个或者零个元素的时候，则不用经行反转

        ，直接返回head\*/

        if (head.next==null||head==null){

            return head;

        }

        /\*新的链表的头节点\*/

        ListNode newHead=null;

        while(head!=null){

           ListNode temp=head.next;

           head.next=newHead;

           newHead=head;

           head=temp;

        }

       return newHead;

    }