[LeetCode] Reverse Linked List II 倒置链表之二

[LeetCode] Reverse Linked List II 倒置链表之二

大家好,又见面了,我是全栈君。

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULLm = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given mn satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

很奇怪为何没有倒置链表之一,就来了这个倒置链表之二,不过猜也能猜得到之一就是单纯的倒置整个链表,而这道作为延伸的地方就是倒置其中的某一小段。对于链表的问题,根据以往的经验一般都是要建一个dummy node,连上原链表的头结点,这样的话就算头结点变动了,我们还可以通过dummy->next来获得新链表的头结点。这道题的要求是只通过一次遍历完成,就拿题目中的例子来说,变换的是2,3,4这三个点,那么我们可以先取出2,用front指针指向2,然后当取出3的时候,我们把3加到2的前面,把front指针前移到3,依次类推,到4后停止,这样我们得到一个新链表4->3->2, front指针指向4。对于原链表连说,有两个点的位置很重要,需要用指针记录下来,分别是1和5,因为当2,3,4被取走时,原链表就变成了1->5->NULL,要把新链表插入的时候需要这两个点的位置。1的位置很好找,因为知道m的值,我们用pre指针记录1的位置,5的位置最后才能记录,当4结点被取走后,5的位置需要记下来,这样我们就可以把倒置后的那一小段链表加入到原链表中。代码如下:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        ListNode *dummy = new ListNode(-1);
        dummy->next = head;
        ListNode *cur = dummy;
        ListNode *pre, *front, *last;
        for (int i = 1; i <= m - 1; ++i) cur = cur->next;
        pre = cur;
        last = cur->next;
        for (int i = m; i <= n; ++i) {
            cur = pre->next;
            pre->next = cur->next;
            cur->next = front;
            front = cur;
        }
        cur = pre->next;
        pre->next = front;
        last->next = cur;
        return dummy->next;
    }
};

本文转自博客园Grandyang的博客,原文链接:倒置链表之二[LeetCode] Reverse Linked List II ,如需转载请自行联系原博主。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/107861.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 到底什么是“数据中台”,我用大白话给你说清楚

    到底什么是“数据中台”,我用大白话给你说清楚近几年以来,朋友圈、微博、技术论坛全网挂起了中台的热潮,下图是百度统计给出的趋势图。那么中台未来是会成为主流发展方向,还是昙花一现只是一个热门话题呢?我希望先从“中台”这个名词的来源开始,或许会有一个

  • mybatis返回两个字段数据_java接口接收json数据

    mybatis返回两个字段数据_java接口接收json数据pg数据库中某字段类型为jsonJava实体中对应类型是jsonObject privateJSONObjectinfo;在mybatis的xml中,常规无法直接进行映射,需要自己写一个TypeHandler,自定义一个JSONTypeHandlerPg类具体代码:packagecom.geovis.common.config;importjava.sql.Callable…

  • iOS在地图上WGS84、GCJ-02、BD-09互转解决方案

    iOS在地图上WGS84、GCJ-02、BD-09互转解决方案

  • Okio的使用和源码解析「建议收藏」

    Okio的使用和源码解析「建议收藏」一.javaNIO和堵塞I/O的区别  1.阻塞I/O通信模型:    阻塞I/O在调用InputStream.read()方法时是阻塞的,它会一直等到数据到来时才会返回       2.javaNIO原理及通信模型    JavaNIO是在jdk1.4开始使用的,是一种非阻塞式的I/O    javaNIO的工作原理:      (1)Jav

  • shell数组与awk数组

    shell数组与awk数组1.whilereadlinedo hosts[i++]=$linedone</etc/hosts#遍历foriin${!hosts[@]}do echo”hosts数组的索引:$i,索引对应的值:${hosts[$i]}”done1.数组值的自增[root@manager/tmp/sh/2020-12-09_题]#declare-Aip#声明一个数组ip[root@manager/tmp/sh/2020-12-09_题]#echo

  • SQL LIKE的用法

    SQL LIKE的用法LIKE 是另一个在 WHERE 子句中会用到的指令。基本上,LIKE 能让我们依据一个套式(pattern)来找出我们要的资料。相对来说,在运用 IN 的时候,我们完全地知道我们需要的条件;在运用 BETWEEN 的时候,我们则是列出一个范围。 LIKE 的语法如下:SELECT”栏位名” FROM”表格名” WHERE”栏位名”LIKE{套式}{套式}经

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号