【Day 7 】2023-11-22 - 61. 旋转链表

[azl397985856]

61. 旋转链表

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/rotate-list/

前置知识

• 求单链表的倒数第 N 个节点

  题目描述

  
  给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: 1->2->3->4->5->NULL, k = 2 输出: 4->5->1->2->3->NULL 解释: 向右旋转 1 步: 5->1->2->3->4->NULL 向右旋转 2 步: 4->5->1->2->3->NULL 示例 2:

输入: 0->1->2->NULL, k = 4 输出: 2->0->1->NULL 解释: 向右旋转 1 步: 2->0->1->NULL 向右旋转 2 步: 1->2->0->NULL 向右旋转 3 步: 0->1->2->NULL 向右旋转 4 步: 2->0->1->NULL

[RealDuxy]

题目名称

旋转链表

题目链接

题目链接

题目思路

拆解链表，重新拼接，重点在于找到断点以及拼接操作

题目代码

# 这里写下解决问题的Python代码
class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if not head or not head.next or k == 0: return head

        # 特殊情况直接得到答案
        total_length = 1
        node = head
        while node.next:
            # print(node.next.val)
            node = node.next
            total_length += 1
        print("final total length: ", total_length)

        if k == total_length:
            return head
        if k > total_length:
            k = k % total_length
        print("final k: ", k)

        if k == 0:
            return head

        # 本质上是找到断点，然后将断电后的链表移位
        peak_node = head
        for _ in range(total_length-k-1):
            peak_node = peak_node.next
        print(peak_node.val)

        post_peak_node = peak_node.next
        new_head = post_peak_node
        print(k)
        for _ in range(k-1):
            post_peak_node = post_peak_node.next
            print(post_peak_node.val)

        post_peak_node.next = head
        peak_node.next=None

        return new_head

## 复杂度
时间: O(n)
空间:O(1)

[adfvcdxv]

思路

循环链表

代码

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var rotateRight = function (head, k) {
    if (!head || k === 0) return head;  // 特判
    let copyHead = head
    let pre = head
    let length = 1
    while (pre.next) {
        pre = pre.next
        length++
    }
    pre.next = copyHead
    let move = length - k % length
    while (move--) {
        pre = pre.next
    }
    copyHead = pre.next
    pre.next = null
    return copyHead
};

复杂度分析

时间复杂度：O(n)。

空间复杂度：O(1)。

[Danielyan86]

solution

分析题目之后想到了用环形链表解决，先闭环，找到对应节点后再断开 需要注意这几点：

• 搞清楚断开的边界节点
• k 的值可能大于链表长度 n，使用取余数方法让 k 小于 n（k%=step），因为整数部分其实就是 n 的倍数
• 如果刚好是整数倍，直接返回，不用再构造环

code

class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if head is None or head.next is None: return head
        cur = head
        step = 0

        # calculate node number
        while cur:
            step += 1
            pre = cur
            cur = cur.next
        k %= step #use remainder to re-calculate the k
        if k == 0: return head
        pre.next = head #make loop link

        for i in range(step - k):
            pre = pre.next
        new_head = pre.next
        pre.next = None
        return new_head

complexity

n is the length of the link

• space: O(n)
• time: O(2n-(step%k))

[joe-the-plumber]

官方题解的python最好改一下。。。现在版本实在不行。。。

anyway, c++ here, we go!

//    获取链表的长度
//   k = k % 链表的长度

//   获取倒数第k + 1,倒数第K个节点与链表尾节点
//   倒数第k + 1个节点.next = null
//   链表尾节点.next = head
//   return 倒数第k个节点
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 != nullptr) {
            cur = cur->next;
            len++;
        }

        k %= len;

        ListNode* fast = head;
        ListNode* slow = head;

        while (fast->next != nullptr) {
            // slow wait k times
            if (k-- <= 0) {
                slow = slow->next;
            }
            fast = fast->next;
        }

        fast->next = head;
        ListNode* new_head = slow->next;
        slow->next = nullptr;
        return new_head;
    }
}

[Junru281]

Leetcode 61 Nov 21

61.Rotate List

Ideas

我是直接粗暴上手List, :( 每一次循环找到last node.next = head, last node的前一个.next设定为null. 直接暴力用for loop.

Mistakes:

1. 没考虑edge case, when empty list, only one node
2. 没考虑k>>n, 根据评论区小伙伴的提醒, 发现可以用modulus方法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(head == null) return null;
        if(head.next == null) return head;
        int n = 1;
        ListNode node = head;
        while(node.next != null){
            node = node.next;
            n++;
        }
        k = k%n;
        for(int i =0; i<k; i++){
            ListNode rotate_node = head;
            ListNode rotate_node_prev = head;
            while(rotate_node.next != null){
                rotate_node_prev = rotate_node;
                rotate_node = rotate_node.next;
            }
            rotate_node_prev.next = null;
            rotate_node.next = head;
            head = rotate_node;
        }
        return head;
    }
}

[witerth]

【Day 7】61. 旋转链表

61. 旋转链表

思路

第一次遍历时，计算链表长度l，算出新的k（k可能比l大，newK = k % l），并且首尾连接。第二次遍历找到新链表的最后一个节点（旧链表的第 l - newK 个节点），将闭合链表断开。

如果k为l的倍数，则新旧链表相同，直接返回旧链表

代码

var rotateRight = function(head, k) {

if (k === 0 || !head || !head.next) return head;

var l = 1;

var cur = head;

while (cur.next) {

​ cur = cur.next;

​ l++;

}

var n = l - k % l;

if (n === l) {

​ return head;

}

cur.next = head;

while (n) {

​ cur = cur.next;

​ n--;

}

var newHead = cur.next;

cur.next = null;

return newHead;

};

复杂度分析

- 时间复杂度：O(N) - 空间复杂度：O(1)

[EggEggLiu]

思路

快慢指针，注意k>链表长度的情况

代码

/**
 * 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) return head;
        ListNode* cur = head;
        int len = 1;
        while (cur->next) {
            cur = cur->next;
            ++len;
        }
        k %= len;
        ListNode* first = head;
        ListNode* second = head;
        while (k--) {
            first = first->next;
        }
        while (first->next) {
            first = first->next;
            second = second->next;
        }
        first->next = head;
        ListNode* newHead = second->next;
        second->next = nullptr;
        return newHead;
    }
};

复杂度

O(N)

[Chloe-C11]

使用计算长度和反转

全部reverse之后，分成两部分再reverse

1. 翻转整个链表，得到新的链表头节点。
2. 翻转前半部分链表，得到新的前半部分链表头节点。
3. 翻转后半部分链表，得到新的后半部分链表头节点。
4. 找到前半部分链表的末尾，将其指向后半部分链表的头节点，完成链表的拼接。
5. 返回新的前半部分链表头节点。

时间复杂度为O(n)

空间复杂度为O(1)

class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        # 特殊条件的判断
        if not head or not head.next or k == 0:
            return head

         # 计算链表长度
        length = 1
        cur = head
        while cur.next:
            cur = cur.next
            length += 1

        # 计算实际需要移动的步数
        k = k % length
        if k == 0: 
            return head

        # 翻转整个链表
        pre = None
        cur = head
        while cur:
            cur.next, pre, cur = pre, cur, cur.next

        # 翻转前半部分链表
        cur = pre
        pre = None
        while k:
            cur.next, pre, cur = pre, cur, cur.next
            k -= 1
        new_start_part = pre

        # 翻转后半部分链表
        pre = None
        while cur:
            cur.next, pre, cur = pre, cur, cur.next

        # 找到前部分链表的末尾，两部分拼接
        cur = new_start_part
        while cur.next:
            cur = cur.next
        cur.next = pre

        return new_start_part

快慢指针

1. 使用快慢指针找到倒数第k个节点的前一个节点。
2. 移动慢指针和快指针，直到快指针到达链表末尾。
3. 重新连接链表，将慢指针的下一个节点作为新的头节点，将快指针的下一个节点指向原来的头节点。
4. 返回新的头节点。

class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        # 特殊条件的判断
        if not head or not head.next or k == 0:
            return head

        # 计算链表长度
        length = 1
        cur = head
        while cur.next:
            cur = cur.next
            length += 1

        # 计算实际需要移动的步数
        k = k % length
        if k == 0:
            return head

        # 找到倒数第k个节点的前一个节点
        slow = fast = head
        for _ in range(k):
            fast = fast.next

        # 移动slow和fast指针，直到fast指针到达链表末尾
        while fast.next:
            slow = slow.next
            fast = fast.next

        # 重新连接链表
        new_head = slow.next
        slow.next = None
        fast.next = head

        return new_head

[laurallalala]

class Solution(object):
    def rotateRight(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        l = 0
        p = head
        while p:
            p = p.next
            l += 1
        k = k%l
        if k == 0:
            return head
        dh = ListNode(-1, head)
        right = dh
        for i in range(k):
            right = right.next
        prev = dh
        while right.next:
            prev = prev.next
            right = right.next
        newh = prev.next
        right.next = head
        prev.next = None
        return newh

Time: O(n) Space: O(1)

[javajianghu]

题目

[61. 旋转链表)

解题思路

思路

1、旋转列表，旋转一次，表示最后一个节点变成头节点，而且next变成之前的head，然后倒数第二个节点变成最后的节点，并且对应的next要变成null

2、那么就遍历链接长度，获取到最后一个节点，然后把last作为newHead，做完以后会有一个问题，就是最后一个节点应该指向null，但是现在指向的是之前的last

3、为了解决第2步遗留的问题，还需要再遍历下newHead,当newHead中的长度和之前head的长度一致时，就把最后一个节点的next改为null，这样newHead就正确了。

关键点在于找到移动k次和链表长度的关系，这样才能减少循环次数

代码

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

        // 获取链表的长度
        int count = 1;
        ListNode next = head;
        while(next.next != null){
            count++;
            next = next.next;
        }
        // 如果移动k次和链表长度取余 = 0 表示链表不需要移动就是结果
        if(k % count == 0){
            return head;
        }

        ListNode newHead = head;
        for (int i = 0; i < k % count; i++) {
            ListNode nt = newHead;
            // 链表节点数量
            while(nt.next != null){
                nt = nt.next;
            }
            // 把最后一个节点的next改为之前的head
            nt.next = newHead;
            // 然后把last作为新的head
            newHead = new ListNode(nt.val, nt.next);
            // 这个遍历的操作是为了把最后一个节点的next改为null，当count == x的时候就表示是最后一个节点
            ListNode n = newHead;
            int x = 1;
            while(n.next != null){
                x++;
                n = n.next;
                if(x == count){
                    n.next = null;
                }
            }
        }
        return newHead;
    }

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)

[emergence23]

思路及算法

记给定链表的长度为 n，注意到当向右移动的次数 k≥n 时，我们仅需要向右移动 k  mod  n 次即可。因为每 n 次移动都会让链表变为原状。这样我们可以知道，新链表的最后一个节点为原链表的第 (n−1) − (k  mod  n) 个节点（从 0 开始计数）。

这样，我们可以先将给定的链表连接成环，然后将指定位置断开。

具体代码中，我们首先计算出链表的长度 nnn，并找到该链表的末尾节点，将其与头节点相连。这样就得到了闭合为环的链表。然后我们找到新链表的最后一个节点（即原链表的第 (n - 1) - (k mod n) 个节点），将当前闭合为环的链表断开，即可得到我们所需要的结果。

特别地，当链表长度不大于 1，或者 k 为 n 的倍数时，新链表将与原链表相同，我们无需进行任何处理。

作者：力扣官方题解 链接：https://leetcode.cn/problems/rotate-list/solutions/681812/xuan-zhuan-lian-biao-by-leetcode-solutio-woq1/ 来源：力扣（LeetCode）

Code

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode rotateRight(ListNode head, int k) {

        if (k == 0 || head == null || head.next == null) {
            return head;
        }
        int n = 1;
        ListNode iter = head;
        while (iter.next != null) {
            iter = iter.next;
            n++;
        }
        int add = n - k % n;
        if (add == n) {
            return head;
        }
        iter.next = head;
        while (add-- > 0) {
            iter = iter.next;
        }
        ListNode ret = iter.next;
        iter.next = null;
        return ret;

    }
}

[larscheng]

思路1

观察示例不难发现，右旋k位，实际上的链表操作为：记录原始链表第k位节点，最后一位节点next=头节点，倒数k+1位节点next=null、返回原链表倒数第k位节点

所以核心思路即为：寻找链表倒数第N个节点-----

特殊情况：k超出链表节点个数时，右旋k位等同于右旋k%count，如果k%count==0，则无需旋转

代码流程如下

1. 统计链表节点个数
2. 快慢指针寻找倒数第k+1个节点
3. 进行节点旋转操作

代码

class Solution{
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k==0) {
            return head;
        }
        ListNode result;
        int len = 1;
        //统计链表节点个数
        ListNode current = head;
        while (current.next != null) {
            current = current.next;
            len++;
        }
        k = k % len;
        if (k == 0) {
            return head;
        }
        //寻找倒数第k+1位
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null) {
            if (k <= 0) {
                slow = slow.next;
            }
            fast = fast.next;
            k--;
        }
        //进行旋转操作
        result = slow.next; //记录倒数第k位（原始链表中倒数k+1位的next）
        fast.next = head;   //最后一位节点next=头节点
        slow.next = null;   //倒数k+1位节点next=null
        return result;
    }
}

复杂度

• 时间复杂度：O(N)
• 空间复杂度：O(1)

  思路2

  n个刻度的环形密码锁，旋转到指定位置 将链表练成环，找到目标位置length-(k%length)，断开链表环

  代码

  class Solution {
  public ListNode rotateRight(ListNode head, int k) {
      if (head == null || head.next == null || k==0) {
          return head;
      }
      int len = 1;
      //统计链表节点个数
      ListNode current = head;
      while (current.next != null) {
          current = current.next;
          len++;
      }
      //成环
      current.next = head;
      //寻找断环节点
      int index = len - (k % len) ;
      for (int i = 1; i < index; i++) {
          head = head.next;
      }
      //断开链表环
      ListNode result = head.next; 
      head.next = null;   //断开环
      return result;
  }
  }

  复杂度

• 时间复杂度：O(N)
• 空间复杂度：O(1)

[ycan253]

思路

1. 计算链表总体长度，得到链表末尾节点的指针，连接至头
2. 找到倒数第k个节点，把这个节点和下一个节点当做新的头尾

代码

 class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if not head or not head.next: return head
        p, list_len = head, 1
        while p.next:
            list_len += 1
            p = p.next
        tail = p
    p, k = head, k % list_len
    if k == 0: return head

    for _ in range(list_len - k - 1):
        p = p.next
    new_tail, new_head = p, p.next
    new_tail.next = None
    tail.next = head
    return new_head

复杂度分析

时间：O(n)

空间：O(1)

[freeroo2]

思路

双指针找到倒数第k个节点

代码

public ListNode rotateRight(ListNode head, int k) {
        if (k == 0 || head == null || head.next == null) {
            return head;
        }
        ListNode tail = head;
        // tail先走k%n步
        for (int i = 0; i < k; i++) {
            if (tail.next == null) {
                tail = head;
            } else {
                tail = tail.next;
            }
        }

        ListNode pre = head;
        while (tail.next != null) {
            tail = tail.next;
            pre = pre.next;
        }
        // 截断、拼接pre后面的节点至表前
        tail.next = head;
        head = pre.next;
        pre.next = null;
        return head;
    }

[rennzhang]

题目

61. 旋转链表

思路

整体思路是用while找到链表最后一个节点，同时将所有的节点按照next顺序记录到数组中去

然后应该算出一个最小的操作数，即k % 链表的节点个数，余数就是需要操作的次数，其他的都是多余操作

可以按照算出的操作次数倒序遍历record逐个进行链表节点修改，但其实可以合并为一次操作：

• 即从record数组中倒数 k+1 一直到数组中最后一个“这一串”链表就是需要操作的结点
• 直接把这一串拼到原链表最前方即可，也就是只需要修改一次即可

代码

class Solution:
    def rotateRight(self, head, k: int) -> ListNode:
        if not k or not head or not head.next: return head
        # 用数组记录所有的指针
        record = [head]

        endNode = head
        while endNode.next:
            endNode = endNode.next
            record.append(endNode)

        # 去掉多余的操作
        k = k % len(record)
        if not k: return head 

        # 从数组记录中取出需要旋转的串，直接拼到最前端
        pre = record[-(k+1)]
        newHead = pre.next
        record[-1].next = head
        pre.next = None

        return newHead

复杂度分析

• 时间复杂度：O(N)

  while 遍历，最大长度是链表的长度，即 N

• 空间复杂度：O(N)

  开辟的新数组长度同样为链表的长度，所以也是N

[JinhMa]

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) return head;
        ListNode cur = head;
        int len = 0;
        while (cur != null) {
            len++;
            cur = cur.next;
        }
        k %= len;
        if (k == 0) return head;
        // 快指针 fast 先走k步：
        ListNode fast = head;
        while (k > 0) {
            fast = fast.next;
            k--;
        }
        ListNode slow = head;
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        ListNode newHead = slow.next;
        slow.next = null;
        fast.next = head;
        return newHead;
    }
}

[snmyj]

class Solution { public: ListNode rotateRight(ListNode head, int k) { if (k == 0 || head == nullptr || head->next == nullptr) { return head; } int n = 1; ListNode iter = head; while (iter->next != nullptr) { iter = iter->next; n++; } int add = n - k % n; if (add == n) { return head; } iter->next = head; while (add--) { iter = iter->next; } ListNode ret = iter->next; iter->next = nullptr; return ret; } };

[Dr-kkk]

思路：

先遍历一遍链表获得长度，再找到第n-k个节点的位置，将tail和head相连，将第n-k+1个节点设置为头，断开第n-k个节点和第n-k+1个节点；

代码

class Solution
{
public:
    ListNode *rotateRight(ListNode *head, int k)
    {
        if (head == nullptr || k == 0)
            return head;
        int len = 1;
        ListNode *tail, *p = head;
        while (p->next != NULL)
        {
            p = p->next;
            len++;
        }
        tail = p;
        k %= len;
        p = head;
        for (int i = 0; i < len - k - 1; i++)
        {
            p = p->next;
        }
        tail->next = head;
        head = p->next;
        p->next = nullptr;
        return head;
    }
};

时间复杂度：n 空间复杂度：n

[Luster-lyl]

/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var rotateRight = function(head, k) {
    if(k===0 || !head || !head.next) return head
    let n = 1;
    let cur = head
    while(cur.next) { // 链表长度
        cur = cur.next
        n++;
    }
    let add = n - k % n
    if(add === n){
        return head
    }

    cur.next = head; // 收尾相连

    // 开始向后旋转
    while (add) {
        cur = cur.next;
        add--;
    }

    const res = cur.next;
    cur.next = null; // 断开
    return res;
};

time: O(n) space: O(1)

[smallppgirl]

思路： 倒数 第 k % len 个节点为 head

class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if k == 0 or not head or not head.next:
            return head

        len = 1
        cur = head
        while cur.next:
            cur = cur.next
            len += 1

        if not (k := k % len):
            return head

        cur.next = head  # tail link to head

        n = len - k
        while n:
            cur = cur.next
            n -= 1

        ret = cur.next
        cu.next = None
        return ret

时间复杂度 O(n) 空间复杂度 O(1)

[qingkediguo]

public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null) {
            return head;
        }
        if (k == 0) {
            return head;
        }
        ListNode tail = head;
        ListNode newtail = head;
        ListNode newHead;
        int len = 1;
        while (tail.next != null) {
            tail = tail.next;
            len = len + 1;
        }
        tail.next = head;
        for (int i = 0; i < (len - k % len - 1); i++) {
            newtail = newtail.next;
        }
        newHead = newtail.next;
        newtail.next = null;

        return newHead;
    }