经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 其他 » 职业生涯 » 查看文章
互联网大厂算法面试题之旋转链表
来源:cnblogs  作者:公众号程序员小熊  时间:2021/5/6 17:44:50  对本文有异议

 

今天带来一道来自互联网大厂(字节、腾讯、微软、苹果等) 面试题 Leetcode 61. 旋转链表,提供 "虚拟头节点 + 双指针" 的解题思路,采用 "动图" 的方式进行层层剖析,供大家参考,希望对大家无论是刷题还是面试都有所帮助。

61. 旋转链表

描述

给你一个链表的头节点 head ,旋转链表,将链表每个节点向右移动 k 个位置。

解题思路

思考

考虑以下几种情况:

特殊情况

  1. 链表为空或只有一个节点;
  2. k 的值为 0 或者为链表长度 L 的整数倍(N > 0)。

一般情况

  1. 链表至少有两个节点且 k 既不等于 0 也不等于 L 的整数倍。

思路

  • 特殊情况
  1. 链表为空或只有一个节点,只要返回头节点即可;
  2. 判断 k == 0,如果等于 0,则直接返回头节点,否则求链表长度 L,再判断 k == NL,如果等于,也可直接返回。
  • 一般情况
  1. 采用 虚拟头节点 + 双指针 的方法,具体如下栗子分析。
举栗

以链表 1->2->3->4->5,k = 2 为栗子,如下图所示。

增加虚拟头节点,设置两根快慢指针 fast/slow 指向它;

先让快指针 fast 向前移动 k 步,慢指针 slow 保持不动; 

快慢指针 fast/slow 同时向前移动,直至快指针指向尾节点;

让快指针 fast 指向的节点指向链表的头节点; 

将慢指针 slow 指向的节点的下一节点设置为新链表的头节点; 

将慢指针 slow 指向的节点设置为新链表的尾节点 slow->next = null; 

旋转原链表后得到新链表。 

 完整动图

反思

  1. 如何找到旋转之后得到的新链表的头节点?

采用 双指针 中的 快慢指针

  1. 设置虚拟头节点的作用?

本题设置 虚拟头节点 的作用是找到 新链表的头节点和尾节点。通过 快慢指针 去寻找。

Show me the Code

C++

  1. 1 ListNode* rotateRight(ListNode* head, int k) {
  2. 2 /* 特殊情况判断 */
  3. 3 if (head == nullptr || head->next == nullptr || k == 0) {
  4. 4 return head;
  5. 5 }
  6. 6
  7. 7 /* 增加虚拟头节点 */
  8. 8 ListNode* dummy = new ListNode(0);
  9. 9 dummy->next = head;
  10. 10
  11. 11 /* 获取链表长度 */
  12. 12 int len = 0;
  13. 13 for (ListNode* node = head; node != nullptr; node = node->next) {
  14. 14 len++;
  15. 15 }
  16. 16
  17. 17 k %= len;
  18. 18 /* 判断 k 是否是 len 的整数倍 */
  19. 19 if (k == 0) {
  20. 20 return head;
  21. 21 }
  22. 22
  23. 23 /* 获取新链表的头尾节点 */
  24. 24 ListNode *fast = dummy, *slow = dummy;
  25. 25 for (int i = 0; i < k; ++i) {
  26. 26 fast = fast->next;
  27. 27 }
  28. 28 while (fast->next != nullptr) {
  29. 29 fast = fast->next;
  30. 30 slow = slow->next;
  31. 31 }
  32. 32 fast->next = head;
  33. 33 head = slow->next;
  34. 34 slow->next = nullptr;
  35. 35
  36. 36 /* 释放虚拟头节点 */
  37. 37 delete dummy;
  38. 38
  39. 39 return head;
  40. 40 }
View Code

java

  1. 1 ListNode rotateRight(ListNode head, int k) {
  2. 2 if (k == 0 || head == null || head.next == null) {
  3. 3 return head;
  4. 4 }
  5. 5
  6. 6 ListNode dummy = new ListNode(0);
  7. 7 dummy.next = head;
  8. 8
  9. 9 int len = 0;
  10. 10 for (ListNode node = head; node != null; node = node.next) {
  11. 11 len++;
  12. 12 }
  13. 13
  14. 14 k %= len;
  15. 15 if (k == 0) {
  16. 16 return head;
  17. 17 }
  18. 18
  19. 19 ListNode fast = dummy, slow = dummy;
  20. 20 for (int i = 0; i < k; ++i) {
  21. 21 fast = fast.next;
  22. 22 }
  23. 23 while (fast.next != null) {
  24. 24 fast = fast.next;
  25. 25 slow = slow.next;
  26. 26 }
  27. 27 fast.next = head;
  28. 28 head = slow.next;
  29. 29 slow.next = null;
  30. 30
  31. 31 return head;
  32. 32 }
View Code

原文链接:http://www.cnblogs.com/TanLiuYi00/p/911kobe.html

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号