题目链接

LeetCode

题目描述

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

示例 1：

61. 旋转链表 - 图1

输入： head = [1,2,3,4,5], k = 2
输出： [4,5,1,2,3]

示例 2：

61. 旋转链表 - 图2

输入： head = [0,1,2], k = 4
输出： [2,0,1]

提示：

  • 链表中节点的数目在范围 [0, 500] 内
  • -100 <= Node.val <= 100

  • 0 <= k <= 2 * 109

    解题思路

    方法一：截断重组

    1. /**
    2. * Definition for singly-linked list.
    3. * struct ListNode {
    4. *     int val;
    5. *     ListNode *next;
    6. *     ListNode() : val(0), next(nullptr) {}
    7. *     ListNode(int x) : val(x), next(nullptr) {}
    8. *     ListNode(int x, ListNode *next) : val(x), next(next) {}
    9. * };
    10. */
    11. class Solution {
    12. public:
    13.   ListNode* rotateRight(ListNode* head, int k) {
    14.       if(head==nullptr||head->next==nullptr||k==0){
    15.           return head;
    16.       }
    17.       // 统计结点个数
    18.       int len = 0;
    19.       ListNode* cur = head;
    20.       while(cur){
    21.           len++;
    22.           cur = cur->next;
    23.       }
    24.       // 套圈情况
    25.       if(k%len==0){
    26.           return head;
    27.       }
    28.       // cur指向结果的最后一个结点
    29.       k = len - k%len - 1;
    30.       cur = head;
    31.       while(k--){
    32.           cur = cur->next;
    33.       }
    34.       // 返回头节点为下一个节点
    35.       ListNode* res = cur->next;
    36.       cur->next = nullptr;
    37.       // 链接两个链表
    38.       cur = res;
    39.       while(cur&&cur->next){
    40.           cur = cur->next;
    41.       }
    42.       cur->next = head;
    43.       return res;
    44.   }
    45. };

  • 时间复杂度 O(2n)

  • 空间复杂度 O(1)

    方法一：闭合为环


    /**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
  ListNode* rotateRight(ListNode* head, int k) {
      if(head==nullptr||head->next==nullptr||k==0){
          return head;
      }
      int len = 1;
      ListNode* cur = head;
      while(cur->next){
          len++;
          cur = cur->next;
      }
      cur->next = head;
      cur = head;
      k = len-(k%len)-1;
      while(k--){
          cur = cur->next;
      }
      head = cur->next;
      cur->next = nullptr;
      return head;
  }
};

  • 时间复杂度 O(2n)

  • 空间复杂度 O(1)