亲宝软件园·资讯

展开

互联网大厂算法面试题之旋转链表

公众号程序员小熊 人气:0

大家好,我是 程序员小熊,来自某 大厂 的程序猿,今天带来一道来自互联网大厂(字节、腾讯、微软、苹果等) 面试题 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 ListNode* rotateRight(ListNode* head, int k) {
 2     /*  特殊情况判断  */
 3     if (head == nullptr || head->next == nullptr || k == 0) {
 4         return head;
 5     }
 6 
 7     /*  增加虚拟头节点  */
 8     ListNode* dummy = new ListNode(0);
 9     dummy->next = head;
10 
11     /*  获取链表长度  */
12     int len = 0;
13     for (ListNode* node = head; node != nullptr; node = node->next) {
14         len++;
15     }
16 
17     k %= len;
18     /*  判断 k 是否是 len 的整数倍  */
19     if (k == 0) {
20         return head;
21     }
22 
23     /*  获取新链表的头尾节点  */
24     ListNode *fast = dummy, *slow = dummy;
25     for (int i = 0; i < k; ++i) {
26         fast = fast->next;
27     } 
28     while (fast->next != nullptr) {
29         fast = fast->next;
30         slow = slow->next;   
31     }        
32     fast->next = head; 
33     head = slow->next; 
34     slow->next = nullptr;
35 
36     /*  释放虚拟头节点  */
37     delete dummy;
38     
39     return head;
40 }
View Code

java

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

更多精彩

关注公众号【程序员小熊】

加载全部内容

相关教程
猜你喜欢
用户评论