lc面试准备:Reverse Linked List II

时间:2022-03-15 23:04:22

1 题目

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.

接口

ListNode reverseBetween(ListNode head, int m, int n)

2 思路

采用就地反转链表。找到m节点,之后每读到一个结点,把它插入到m结点前面位置,然后m结点接到读到结点的下一个。
  • 第一步是找到m结点所在位置.
  • 第二步是从节点m到n依次反转指针.

复杂度

Time: O(n) 总共只需要一次扫描,所以时间是O(n)
Space: O(1) 只需要几个辅助指针,空间是O(1)。

3 代码

     public ListNode reverseBetween(ListNode head, int m, int n) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode prev = dummy;
for (int i = 0; i < m - 1; i++) {
prev = prev.next;
}
// 就地反转法
ListNode dummy2 = prev;
prev = dummy2.next;
ListNode pCur = prev.next;
for (int i = m - 1; i < n - 1; i++) {
prev.next = pCur.next;
pCur.next = dummy2.next;
dummy2.next = pCur;
pCur = prev.next;
}
return dummy.next;
}

4 总结

常见的链表反转操作,反转链表的一部分。

5 扩展

熟练掌握链表反转的2种方法,适当运用。

6 参考

  1. 题目
  2. LeetCode:Reverse Linked List II
  3. Reverse Linked List II -- LeetCode

lc面试准备:Reverse Linked List II的更多相关文章

  1. 【leetcode】Reverse Linked List II

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

  2. 14&period; Reverse Linked List II

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

  3. 【原创】Leetcode -- Reverse Linked List II -- 代码随笔(备忘)

    题目:Reverse Linked List II 题意:Reverse a linked list from position m to n. Do it in-place and in one-p ...

  4. 92&period; 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- ...

  5. 【LeetCode练习题】Reverse Linked List II

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

  6. &lbrack;Linked List&rsqb;Reverse Linked List&comma;Reverse Linked List II

    一.Reverse Linked List  (M) Reverse Linked List II (M) Binary Tree Upside Down (E) Palindrome Linked ...

  7. LeetCode之&OpenCurlyDoubleQuote;链表”:Reverse Linked List &amp&semi;&amp&semi; Reverse Linked List II

    1. Reverse Linked List 题目链接 题目要求: Reverse a singly linked list. Hint: A linked list can be reversed ...

  8. leetcode -day30 Reverse Linked List II

    1.  Reverse Linked List II  Reverse a linked list from position m to n. Do it in-place and in one- ...

  9. LeetCode解题报告—— Reverse Linked List II &amp&semi; Restore IP Addresses &amp&semi; Unique Binary Search Trees II

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

随机推荐

  1. 在ubuntu14&period;04设置静态ip

    打开网络的配置文件 sudo vim /etc/network/interfaces 选择网卡,我这里是有线网卡eth0,设置静态ip为192.168.1.108 auto eth0 iface et ...

  2. 了解 JavaScript (6)&ndash&semi; 广告条(Banner&rpar;

    在 Web 上冲浪时,常常会见到定期在图像之间切换的广告条.我们可以用 JavaScript 来实现,重复循环显示它们. 创建循环的广告条 RotatingBanner.html 页面中在循环的广告条 ...

  3. Android模拟器问题:No system images installed for this target

    CPU/ABI选项无法选择,提示:No system images installed for this target,也就是没有适合的系统镜像 打开Android Manager SDK 下载完后重 ...

  4. Hadoop 学习笔记 (十一) MapReduce 求平均成绩

    china:张三 78李四 89王五 96赵六 67english张三 80李四 82王五    84赵六 86math张三 88李四 99王五 66赵六 77 import java.io.IOEx ...

  5. SQL server与Oracle触发器的创建与使用

    SQL Server 1创建触发器 GO BEGIN IF (object_id('WMY', 'tr') is not null) DROP trigger WMY END; GO CREATE T ...

  6. Lucene&period;net入门学习系列&lpar;1&rpar;

    Lucene.net入门学习系列(1)   Lucene.net入门学习系列(1)-分词 Lucene.net入门学习系列(2)-创建索引 Lucene.net入门学习系列(3)-全文检索 这几天在公 ...

  7. Android 5&period;0&lpar;棒棒糖&rpar;&rpar;十大新特性

    Android 5.0(棒棒糖))十大新特性 1. 全新Material Design设计风格 Android Lollipop全新的设计语言是受到了多种因素影响,是一种大胆的平面化创新.换句话说,谷 ...

  8. 初入servlet:Allocate exception for servlet

    老板,来一碗错误垫垫肚子! 如果以下几个错误都符合,估计就是这个原因了. 页面报错如下: java.lang.NoClassDefFoundError:IllegalName: firstDemo/T ...

  9. 去除桌面SVN问号

    由于误操作,桌面文件全部带着问号. 找到一种比较方便的方法解决. 1.显示受保护文件.文件夹win7系统 - 随便打开一个文件夹 -  在菜单栏里点 工具 - 文件夹选项 - 查看 以下如图中选择 2 ...

  10. SQL取最大值编码&lpar;自动编码&rpar;

    SQL取最大值编码(自动编码) 用途 : 使用SQL语法做出自动编码效果,例如将单号自动+1后,产生该笔单号 Table说明 SQL语法 SELECT 'A'+REPLICATE('0',7-len( ...