【Day 7 】2024-08-21 - 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

[akxuan]

先算一下整长度， 然后计算下new head ， 最后操作， 把 new_tail.next 指向空， 然后 prev tail 指向 prev head 就好了 这里两个坑， 一个是算 k 的时候要注意，移动一次， 应该是最后一个element 变成了 head。 第二个是， k的赋值， 最先开始我用了这个方法赋值： k = n - k - 1 导致后续有个判断 k==0， 直接返回了head。

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

        n = 1
        last = head
        while last.next: 
            last = last.next 
            n += 1

        k %= n 
        if k == 0:
            return head

        carry = head

        k1= n-k-1

        for _ in range(  k1):  # Move `n-k-1` times to stop at the new tail
            carry = carry.next

        if not carry.next or k == 0  :
            return head
        else: 
            tmp = carry.next 
            last.next = head 
            carry.next = None 

            return tmp

空间复杂度 O(1) 时间复杂度 O(N), N 为 list 长度

[CelesteXiong]

Intuition

Use modulo to process k to get the times we need to rotate the list. Assuming the number of nodes is n, then we need rotate n % k times. Then we find the (k + 1)-th node from the last and set the next to null. And update the next of the last node to the head node.

Algorithm

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if k == 0 or not head: return head
        length = 0
        node = head
        while node:
            length += 1
            node = node.next
        k = k % length

        node = head
        for i in range(length-k-1):
            node = node.next
        node_new_head = node.next
        node.next = None

        node = node_new_head
        if not node: return head

        while node and node.next:
            node = node.next
        node.next = head
        return node_new_head

Complexity

Time: O(n), n is the number of nodes

Space: O(1)

[zjy-debug]

思路

获得链表长度；计算移动量k；移除前k个节点；创建新链表，移动到链尾，连接两个链表。

代码

class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:

        if head is None:
            return None

        length = 0
        current = head

        while current is not None:
            length += 1
            current = current.next

        k = k % length

        if k == 0:
            return head

        current = head

        for i in range(0, length - k - 1):
            current = current.next

        new_head = current.next
        current.next = None

        tail = new_head
        while tail.next is not None:
            tail = tail.next
        tail.next = head

        return new_head

复杂度

时间: O(n)

空间: O(1)

[jialigogogo]

思路

将链表首位相连，根据偏移量取旋转后的最后一位

代码

public static ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0){
            return head;
        }
        ListNode l = head;
        int max = 1;
        while (l.next != null){
            l = l.next;
            max++;
        }
        // 移动的次数
        int f = k % max;
        if (f == 0){
            return head;
        }
        // 首位相连
        l.next = head;
        ListNode end = head;
        // 获取旋转后的最后一位
        while (++f < max){
            end = end.next;
        }
        ListNode re = end.next;
        end.next = null;
        return re;
    }

复杂度

时间复杂度：O(n)

空间复杂度：O(1)

[panfx]

思路

涉及到链表的，特别是类似旋转K个元素的问题等，优先考虑双指针解法。A指针走K个元素，B指针启动，到A指针走到结尾，B指针此时距离结尾刚好K个元素，此时将A指针元素与当前链表头部相连，再将B指针元素指向NULL

代码

/**
 * 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;
        }
        ListNode result = null;
        ListNode tail = null;
        ListNode a = head;
        ListNode b = head;
        int i = 0;
        while (true) {
            if (a.next == null) {
                a.next = head;
                tail = a;
                if (i < k) {
                    // k对链表长度取余，使k小于链表长度，节约循环时间,重新遍历
                    i++;
                    k = k%i;
                    i = 0;
                    a = head;
                    continue;
                }

            }

            // a指针已遍历到末尾
            if (a == tail) {
                // 判断b指针是否已经启动
                if (i >= k) {
                    result = b.next;
                    b.next = null;
                    break;
                } 
            }

            // 继续移动
            a = a.next;
            if (i >= k) {
                b = b.next;
            }
            i++;
        }

        return result;
    }
}

复杂度

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

[godkun]

思路

数据结构：链表

实现方案：

1. 确定表长度、找到尾节点
2. 确定旋转次数
3. 找到length - k - 1的表节点
4. 尾节点next指向head，3步骤节点变成尾节点

代码

TypeScript实现

function rotateRight(head: ListNode | null, k: number): ListNode | null {
  if (!head || !head.next || k === 0) return head

  let length = 1
  let tail = head
  while (tail.next) {
    tail = tail.next
    length++
  }

  k = k % length
  if (k === 0) return head

  // 找到新的头节点的前一个节点
  let newTail = head
  for (let i = 0; i < length - k - 1; i++) {
    newTail = newTail.next
  }
  // 旋转链表
  const newHead = newTail.next
  newTail.next = null
  tail.next = head

  return newHead
}

复杂度分析

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

[liudi9047]

class Solution(object): def rotateRight(self, head, k): if head is None or head.next is None: return head start, end, len = head, None, 0 while head: end = head head = head.next len += 1 end.next = start pos = len - k % len while pos > 1: start = start.next pos -= 1 ret = start.next start.next = None return ret

[peggyhao]

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;
    }
}

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

[Fightforcoding]

思路

first count the lenth of the list, then make it into a circle, rotate K step, then break the circle

代码

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# first count the lenth of the list, then make it into a circle, rotate K step, then break the circle
class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if k ==0 or not head or not head.next:
            return head
        # count the length
        lenth = 1
        old_head = head
        while head.next:
            head = head.next
            lenth += 1
        #make a circle
        head.next = old_head
        #calculate steps
        k = k % lenth
        steps = lenth - k
        #rorate K steps
        new_tail = old_head
        for _ in range(steps - 1):
            new_tail = new_tail.next
        new_head = new_tail.next
        #break the circle
        new_tail.next = None
        return new_head