LeetCode 61. 旋转链表

题目描述
- 法一：链表闭合成环
- 法二：快慢指针

题目描述

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

地址：https://leetcode-cn.com/problems/rotate-list/
2021/03/27

法一：链表闭合成环
若head null 或 head->next null 直接就返回
若 k = 0 或 k 为 n（链表的长度）的倍数，直接返回原链表
新链表的最后一个节点为原链表的第 (n - 1) - (k mod n)个节点（从 0 开始计数）
- 找到新链表的最后一个节点，将链表断开
时间复杂度 O(n)

空间复杂度 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 n = 1;
      ListNode* tail = head;
      while (tail->next != nullptr) { // 统计链表长度
          tail = tail->next;
          n ++;
      }
      int tmp = n - (k % n);
      if (tmp == n) return head; // n 为 k 的倍数
      tail->next = head; // 闭合
      while (tmp --) { // 判断断开的位置
          tail = tail->next;
      }
      ListNode* ans = tail->next;
      tail->next = nullptr;
      return ans;
  }
};

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
  def rotateRight(self, head, k):
      if not head or not head.next or k == 0:
          return head;
      n = 1
      tail = head
      while tail.next:
          tail = tail.next
          n += 1
      tmp = n - k % n
      if tmp == n:
          return head
      tail.next = head
      while tmp:
          tail = tail.next
          tmp -= 1
      ans = tail.next
      tail.next = None
      return ans

法二：快慢指针

用「快慢指针」找到倒数第 k 个节点即新的链表头
时间复杂度 O(n)

空间复杂度 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 n = 1;
      ListNode* cur = head;
      while (cur->next != nullptr) { // 统计链表的长度
          n ++;
          cur = cur->next;
      } 
      k %= n;
      if (k == 0) return head;
      // 快慢指针遍历链表，slow会停在new head的前一位
      ListNode* slow = head;
      ListNode* fast = head;
      while (k-- > 0) fast = fast->next; // fast 此时与slow 相隔 k，即fast 刚好是 slow 旋转 k 后的位置
      while (fast->next != nullptr) { // 同步往前走，即反转链表的前半部分
          slow = slow->next;
          fast = fast->next;
      }
      ListNode* newHead = slow->next;
      slow->next = nullptr;
      fast->next = head; // 将新链表的前半部分与后半部分拼接
      return newHead;
  }
};

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
  def rotateRight(self, head, k):
      if not head or not head.next or k == 0:
          return head
      n = 1
      cur = head
      while cur.next != None:
          cur = cur.next
          n += 1
      k %= n
      if k == 0:
          return head
      slow = head
      fast = head
      while k > 0:
          fast = fast.next
          k -= 1
      while fast.next != None:
          slow = slow.next
          fast = fast.next
      newHead = slow.next
      slow.next = None
      fast.next = head
      return newHead

题目描述

法一：链表闭合成环

法二：快慢指针