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

会员服务 ·

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

2021 年 11 月 25 日 极市平台

↑ 点击蓝字关注极市平台

作者丨Dine

来源丨程序员小熊

编辑丨极市平台

极市导读

本文介绍一道来自互联网大厂（字节、腾讯、微软等）面试题 Leetcode 61. 旋转链表，提供虚拟头节点 + 双指针的解题思路，采用动图的方式进行层层剖析，供大家参考，希望对大家无论是刷题还是面试都有所帮助。 >>加入极市CV技术交流群，走在计算机视觉的最前沿

旋转链表

描述

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

解题思路

思考

考虑以下几种情况：

特殊情况

链表为空或只有一个节点；
k 的值为 0 或者为链表长度 L 的整数倍（N > 0）。

一般情况

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

思路

特殊情况

链表为空或只有一个节点， 返回头节点即可；
判断 k == 0，如果等于 0，则直接返回头节点，否则求链表长度 L，再判断 k == NL，如果等于，也可直接返回头节点。

一般情况

采用 虚拟头节点 + 双指针 的方法，具体如下栗子分析。

举栗

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

增加虚拟头节点，并让两个快慢指针指向它；

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

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

让 快指针 fast 指向的节点指向链表的头节点，使链表成环；

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

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

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

完整动图

反思

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

采用 双指针 中的 快慢指针 。

设置虚拟头节点的作用？

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

Show me the Code

C++

ListNode* rotateRight(ListNode* head, int k) {  
    /*  特殊情况判断  */  
    if (head == nullptr || head->next == nullptr || k == 0) {  
        return head;  
    }  

    /*  增加虚拟头节点  */  
    ListNode* dummy = new ListNode(0);  
    dummy->next = head;  
      
    /*  获取链表长度  */  
    int len = 0;  
    for (ListNode* node = head; node != nullptr; node = node->next) {  
        len++;  
    }  
      
    k %= len;  
    /*  判断 k 是否是 len 的整数倍  */  
    if (k == 0) {  
        return head;  
    }  
      
    /*  获取新链表的头尾节点  */  
    ListNode *fast = dummy, *slow = dummy;  
    for (int i = 0; i < k; ++i) {  
        fast = fast->next;  
    }   
    while (fast->next != nullptr) {  
        fast = fast->next;  
        slow = slow->next;     
    }          
    fast->next = head;   
    head = slow->next;   
    slow->next = nullptr;  
      
    /*  释放虚拟头节点  */  
    delete dummy;  
      
    return head;  

}

java

ListNode rotateRight(ListNode head, int k) {  
    if (k == 0 || head == null || head.next == null) {  
        return head;  
    }  

    ListNode dummy = new ListNode(0);  
    dummy.next = head;  
      
    int len = 0;  
    for (ListNode node = head; node != null; node = node.next) {  
        len++;  
    }       
      
    k %= len;  
    if (k == 0) {  
        return head;  
    }  
      
    ListNode fast = dummy, slow = dummy;  
    for (int i = 0; i < k; ++i) {  
        fast = fast.next;  
    }   
    while (fast.next != null) {  
        fast = fast.next;  
        slow = slow.next;     
    }          
    fast.next = head;   
    head = slow.next;   
    slow.next = null;  
      
    return head;  

}