文档章节

反转链表 Reverse Linked List

叶枫啦啦
 叶枫啦啦
发布于 2017/06/21 16:21
字数 298
阅读 6
收藏 0

问题:

Reverse a singly linked list.

Hint:

A linked list can be reversed either iteratively or recursively. Could you implement both?

解决:

① 采用头插法,额外创建一个节点,然后将链表一次插入到头节点后面,就完成了反转。耗时0ms.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

public class Solution{
    public ListNode reverseList(ListNode head){
        if(head == null || head.next == null) return head;
        ListNode header = new ListNode(-1);
        ListNode cur = head;
        while(cur != null){
            ListNode next = cur.next;
            cur.next = header.next;
            header.next = cur;
            cur = next;
        }
        return header.next;
    }
}

②迭代法,在遍历节点的时候,将当前节点的next指向它的前一个节点,因此,要预先保存前一个节点和后一个节点。

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

③ 递归法,开始时 n1 → … → nk-1 → nk → nk+1 → … → nm → Ø,我们要反转链表,就会成为     n1 → … → nk-1 → nk → nk+1 ← … ← nm,所以有nk.next.next = nk;

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode p = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return p;
}

© 著作权归作者所有

叶枫啦啦
粉丝 14
博文 583
码字总数 400448
作品 0
海淀
私信 提问
LeetCode 之 JavaScript 解答第206题 —— 反转链表(Reverse Linked List)

Time:2019/4/23 Title: Reverse Linked List Difficulty: Easy Author: 小鹿 题目:Reverse Linked List(反转链表) Reverse a singly linked list. Example: Follow up: A linked list ca......

不甘平凡的小鹿
04/29
0
0
单链表中k个结点一组进行反转

原题   Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.   If the number of nodes is not a multiple of k then left-out nodes......

一贱书生
2016/12/13
19
0
Lintcode36 Reverse Linked List II solution 题解

【题目描述】 Reverse a linked list from position m to n. Notice:Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list. 翻转链表中第m个节点到第n个节点的部分 ......

abcdd1234567890
2017/06/14
0
0
怎样应对IT面试与笔试-(十六)

19. Remove Nth Node From End of List 删除链表的倒数第N个结点 例如 给出列表: 1->2->3->4->5, and n = 2. 删除倒数第二个结点后变为:1->2->3->5 题目限定n总是有效的,且要求我们尽量用一......

Ice_Frog
2018/05/30
0
0
206. Reverse Linked List - LeetCode

Question 206. Reverse Linked List Solution 题目大意:对一个链表进行反转 思路: Java实现:

yysue
2018/07/16
36
0

没有更多内容

加载失败,请刷新页面

加载更多

nginx学习笔记

中间件位于客户机/ 服务器的操作系统之上,管理计算机资源和网络通讯。 是连接两个独立应用程序或独立系统的软件。 web请求通过中间件可以直接调用操作系统,也可以经过中间件把请求分发到多...

码农实战
今天
5
0
Spring Security 实战干货:玩转自定义登录

1. 前言 前面的关于 Spring Security 相关的文章只是一个预热。为了接下来更好的实战,如果你错过了请从 Spring Security 实战系列 开始。安全访问的第一步就是认证(Authentication),认证...

码农小胖哥
今天
12
0
JAVA 实现雪花算法生成唯一订单号工具类

import lombok.SneakyThrows;import lombok.extern.slf4j.Slf4j;import java.util.Calendar;/** * Default distributed primary key generator. * * <p> * Use snowflake......

huangkejie
昨天
12
0
PhotoShop 色调:RGB/CMYK 颜色模式

一·、 RGB : 三原色:红绿蓝 1.通道:通道中的红绿蓝通道分别对应的是红绿蓝三种原色(RGB)的显示范围 1.差值模式能模拟三种原色叠加之后的效果 2.添加-颜色曲线:调整图像RGB颜色----R色增强...

东方墨天
昨天
11
1
将博客搬至CSDN

将博客搬至CSDN

算法与编程之美
昨天
13
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部