同系列文章导读:【数据结构与算法】导读

所有文章均在本博客首发,其他平台同步更新

如果有更好的方法,欢迎指点,共同进步~~

有其他语言代码也可在留言区留言,谢谢

发表评论时请填写正确邮箱,以便于接收通知【推荐QQ邮箱】


  • 时间:2022-05-15
  • 题目序号:206
  • 难度:简单

问题描述

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

来源:力扣(LeetCode)

示例1

img

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

示例2

img

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

示例3

输入:head = []
输出:[]

提示

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

解题思路

题解部分参考自代码随想录。如有侵权,请联系进行删除~~
  • 本题可以通过双指针或者递归两种方法解决,基本思路一样
  • 需要改变链表的next指针的指向,直接将链表反转 ,如图所示:

  • 可以通过定义两个指针:cur和pre
  • cur指向当前结点,pre指向前一个结点

img

  • 如图,使用一个临时变量temp记录cur.next结点
  • 然后将cur.next = pre(逐个进行反转)
  • 再将pre和cur指针后移(pre = cur、cur = temp)
  • 通过不断地循环,最后pre指向的就是最后一个结点,也就是反转后的头结点,直接返回即可

代码实现

双指针法

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

递归

  • 递归相对于抽象一些,但是基本思路都一样
  • 首先明确递归结束的条件,然后进行递归调用
  • 在理解双指针法后,理解递归也会容易一些
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode cur = head, prev = null;
        return reserve(prev, cur);
    }
  
    public ListNode reserve(ListNode prev, ListNode cur){
        if(cur == null) return prev;
        ListNode temp = cur.next;
        cur.next = prev;
        return reserve(cur, temp);
    }
}

总结

  • 本题比较简单,两种方法思路一样,只不过代码写法略有不同
  • 在使用递归方法时,一定要首先确认递归结束条件,并做出判断(否则递归就会无休止的调用下去)
最后修改:2022 年 05 月 15 日
如果觉得我的文章对你有用,请随意赞赏