数据结构与算法 | Leetcode 206:Reverse Linked List

栏目: 编程工具 · 发布时间: 5年前

内容简介:前面我们实现了几种常见的链表 ,接下来,我们来聊聊如何实现示例:
数据结构与算法 | Leetcode 206:Reverse Linked List

前面我们实现了几种常见的链表 ,接下来,我们来聊聊如何实现 单链表 的反转。

链表反转

Leetcode 206: Reverse Linked List

示例:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Input: NULL
Output: NULL
复制代码

我们可以通过循环遍历和递归这两种方式来实现链表的反转。

遍历

思路

定义三个指针,分别为prev、curr、next,然后遍历所有node结点,并移动这三个指针,改变curr结点的next指向,指向prev结点,实现linkedList的反转。

数据结构与算法 | Leetcode 206:Reverse Linked List

代码实现

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        ListNode next = null;
        while(curr != null){
            next = curr.next;
            curr.next = prev;        
            prev = curr;
            curr = next;
        }
        head = prev;
        return head; 
    }
}
复制代码

源码

递归

其实递归的实现方式和前面循环的方式非常相似,前者是通过循环来移动指针,后者是通过递归来移动指针。

定义一个递归接口,传入curr与prev节点作为参数,内部再将curr的作为下次递归调用的prev入参, curr.next 作为下次递归调用的curr入参。

代码实现

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    
    public ListNode reverseList(ListNode head){
        return reverseRecursively(head, null);
    }
    
    public ListNode reverseRecursively(ListNode curr, ListNode prev) {
        if(curr == null){
            return null;
        }
        if(curr.next == null){
            ListNode head = curr;
            curr.next = prev;
            return head;
        }
        
        ListNode next1 = curr.next;
        curr.next = prev;
        
        ListNode head = reverseRecursively(next1, curr);
        return head;
    }
}
复制代码

源码

这两种方式的时间复杂度均为O(n),空间复杂度均为O(1)。


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

微服务设计

微服务设计

[英] Sam Newman / 崔力强、张 骏 / 人民邮电出版社 / 2016-5 / 69.00元

本书全面介绍了微服务的建模、集成、测试、部署和监控,通过一个虚构的公司讲解了如何建立微服务架构。主要内容包括认识微服务在保证系统设计与组织目标统一上的重要性,学会把服务集成到已有系统中,采用递增手段拆分单块大型应用,通过持续集成部署微服务,等等。一起来看看 《微服务设计》 这本书的介绍吧!

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具