温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

LeetCode怎样反转链表

发布时间:2021-12-15 15:01:17 来源:亿速云 阅读:160 作者:小新 栏目:大数据

这篇文章主要为大家展示了“LeetCode怎样反转链表”,内容简而易懂,条理清晰,希望能够帮助大家解决疑惑,下面让小编带领大家一起研究并学习一下“LeetCode怎样反转链表”这篇文章吧。

题目描述

反转一个单链表。

 

示例:

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

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

 

解题思路

链表一般都是用迭代或是递归法来解决,而且一般都是构造双指针、三指针,比如反转链表或是DP动态规划。

 

双指针迭代

我们可以申请两个指针,第一个指针叫 pre,最初是指向 null 的。

第二个指针 cur 指向 head,然后不断遍历 cur。

每次迭代到 cur,都将 cur 的 next 指向 pre,然后 pre 和 cur 前进一位。

都迭代完了(cur 变成 null 了),pre 就是最后一个节点了。

java实现

class Solution {
 public ListNode reverseList(ListNode head) {
  //申请结点,pre和 cur,pre指向null
  ListNode pre = null;
  ListNode cur = head;
  ListNode tmp = null;
  while(cur!=null) {
   //记录当前节点的下一个节点
   tmp = cur.next;
   //然后将当前节点指向pre
   cur.next = pre;
   //pre和cur节点都前进一位
   pre = cur;
   cur = tmp;
  }
  return pre;
 }
}
 

Python实现

class Solution(object):
    def reverseList(self, head):
        if not head or not head.next:
            return head
        l = head 
        r = head.next 
        remain = r.next 
        l.next = None
        while r:
            r.next = l 
            l = r 
            r = remain 
            if remain:
                remain = remain.next
        return l
   

递归实现:

递归的两个条件:

  • 终止条件是当前节点或者下一个节点==null
  • 在函数内部,改变节点的指向,也就是 head 的下一个节点指向 head 递归函数那句     head.next.next = head很不好理解,其实就是 head 的下一个节点指向head。

递归函数中每次返回的 cur 其实只最后一个节点,在递归函数内部,改变的是当前节点的指向。

class Solution {
 public ListNode reverseList(ListNode head) {
  //递归终止条件是当前为空,或者下一个节点为空
  if(head==null || head.next==null) {
   return head;
  }
  //这里的cur就是最后一个节点
  ListNode cur = reverseList(head.next);
  //如果链表是 1->2->3->4->5,那么此时的cur就是5
  //而head是4,head的下一个是5,下下一个是空
  //所以head.next.next 就是5->4
  head.next.next = head;
  //防止链表循环,需要将head.next设置为空
  head.next = null;
  //每层递归函数都返回cur,也就是最后一个节点
  return cur;
 }
}
 
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or head.next == None: return head
        res = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return res

以上是“LeetCode怎样反转链表”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注亿速云行业资讯频道!

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI