【Day 7 】2024-04-14 - 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

[zhiyuanpeng]

class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if not head:
            return head
        if not k:
            return head
        # get the length of head
        p = head
        length = 0
        while p:
            length += 1
            p = p.next
        _, k = divmod(k, length)
        if not k:
            return head
        # start rotateRight, find the length-k node
        loc = 0
        p = head
        while p:
            loc += 1
            if loc == length - k:
                break
            else:
                p = p.next
        new_head = p.next
        p.next = None
        pointer = new_head
        while pointer.next:
            pointer = pointer.next
        pointer.next = head
        return new_head

time O(N) space O(1)

[coderXiaowq]

Java 时间复杂度 O(n) 面向debug编程......

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(head==null || k == 0) return head;
        //先获取链表长度 计算head偏移距离
        ListNode cur = head;
        int N = 1;
        while(cur.next!=null){
            cur = cur.next;
            N++;
        }
        if(N == 1) return head;
        k %= N;//计算实际偏移量 
        if(k==0) return head;
        cur.next = head;//将链表闭合 
        //利用cur找位置
        cur = head;
        while(k<N-1){
            cur = cur.next;
            k++;
        }
        //cur指向要切开元素对左边那个 切断 0-1-2/-3-4
        ListNode temp = cur.next;
        cur.next = null;
        return temp;
    }
}

[GReyQT]

题解思路：

（1）计算链表长度并找到尾节点 （2）形成环形链表减少尾处理 （3）将 k 取模，减少多余操作 （4）从头节点到新头节点的步数，找到新的尾节点，断开链表

代码：

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) 
    {
        if (head == nullptr || k == 0)
        {
            return head;
        }
        ListNode* tail = head;
        int len = 1;
        while (tail->next)  //计算链表长度并找到尾节点
        {
            len++;
            tail = tail->next;
        }
        tail->next = head; //形成环形链表减少尾处理；
        k = k % len; //将 k 取模，减少多余操作
        int step = len - k;//计算从头节点到新头节点的步数
        ListNode* newtail = head;
        for (int i = 1; i < step; ++i)
        {
            newtail = newtail->next;//找到新的尾节点
        }
        ListNode* newhead = newtail->next;// 新的头节点
        newtail->next = nullptr;//断开链表
        return newhead;
    }
};

复杂度分析：

• 时间复杂度：取决于链表的长度n，因此时间的复杂度为O(n)
• 空间复杂度：函数额外创建变量存储指针和普通变量，因此空间复杂度为 O(1)

[Dtjk]

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        ListNode* newhead=head,*forward=head,*temp=head;
        int count=1;
        if(!head) return nullptr;
        while(temp->next){
            temp=temp->next;
            count++;
        }
        k=k%count;
        for(int i=0;i<k;i++){
            forward=forward->next;
        }
        while(forward->next){
            newhead=newhead->next;
            forward=forward->next;
        }
        forward->next=head;
        head=newhead->next;
        newhead->next=nullptr;

        return head;
    }
};

[xil324]

var rotateRight = function(head, k) {
    if(!head) return head;
    let length = 0;
    let node = head;
    while(node) {
        node = node.next;
        length += 1;
    }
    k = k % length;
    let slow = head, fast = head, result = head;
    while(fast.next) {
        fast = fast.next;
        k -= 1;
        if(k < 0) {
            slow = slow.next; 
        }
    }
    fast.next = head;
    result = slow.next;
    slow.next = null
    return result;
};

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

[rao-qianlin]

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null) {
            return head;
        }

        ListNode end = head;
        int len = 1;

        while (end.next != null) {
            end = end.next;
            len += 1;
        }
        // return new ListNode(len);
        // end 位于链表尾部 len为链表长度
        // 连接形成环形链表

        end.next = head;
        // 处理k，如果k大于len，则减去len
        while (k >= len) {
            k -= len;
        }
        if (k == 0) {
            // 不进行旋转
            end.next = null;
        } else {
            // 找到链表第 len-k 个节点，就是新的尾结点
            ListNode pre = head;
            for (int i = 0; i < len - k - 1; i++) {
                pre = pre.next;
            }
            // pre.next 就是新的头结点；
            head = pre.next;
            // 断开环
            pre.next = null;

        }

        return head;

    }
}

[CathyShang]

思路： 参考题解

• 当链表长度小于1，k==0时，原链表输出；
• 计链表长度n；
• 当k%n==0时，原链表输出；
• 链表成环

• 在p = n-k%n处断开，输出 代码：

  class Solution {
  public:
  ListNode* rotateRight(ListNode* head, int k) {
      //当链表为空，或者长度为1，k=0
      //head->next==nullptr||head==nullptr||k==0 报错[]
      if(k==0||head==nullptr||head->next==nullptr){
          return head;
      }
      int n=1;
      //计数
      ListNode* cur = head;
      while(cur->next!=nullptr){
          cur = cur->next;
          n++;
      }
      //此时，cur指向尾节点
  
      //计算在哪里断开
      int part = n-k%n;
      if(part==n){
          return head;
      }
      //成环
      cur->next = head; //cur指向头部        
      while(part>0){
          cur = cur->next;
          part--;
      }
      // 旋转后，cur指向链表尾节点
      ListNode* res=cur->next; // 现在还是环，指向答案头部
      // 断开
      cur->next = nullptr;
      return res;
  }
  };

  复杂度：

• 时间复杂度 $O(N)$
• 空间复杂度 $O(1)$ 这里均使用指针

[eclairs46]

var rotateRight = function(head, k) { if (!head || !head.next || k === 0) return head;

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

let newTail = head;
for (let i = 0; i < length - k % length - 1; i++) {
    newTail = newTail.next;
}

let newHead = newTail.next;
newTail.next = null;
return newHead;

};

[hillsonziqiu]

思路

链表如果拼成一个“轮子”的话，那么就容易解决了。

实现

var rotateRight = function (head, k) {
  if (!head || !head.next || k === 0) return head;

  let [n, cur] = [1, head];
  while (cur.next) {
    cur = cur.next;
    n++;
  }

  let gap = n - (k % n);
  if (gap === n) return head;

  cur.next = head;
  while (gap > 0) {
    cur = cur.next;
    gap--;
  }

  const res = cur.next;
  cur.next = null;

  return res;
};

复杂度分析

时间复杂度：O(n) 最多循环2次 故时间复杂度为O(n) 空间复杂度：O(1)

[Martina001]

// 这个题的自己做的时候错误在于，使用了固化的数组的思维去做一个链表题，后移几个节点，直接断掉再连即可，不用单纯的一个个后移

    // 这个题应该是直接闭环，然后在k%n处断掉即可
    if(head == null || k==0 || head.next == null){
        return head;
    }
    ListNode temp = head;
    int n = 1;
    while(temp.next != null){
        n++;
        temp=temp.next;
    }
    int i = k%n;
    if(i==0){
        return head;
    }
    temp.next = head;
    int needMove = n-i;
    while(needMove-- > 0){
        temp = temp.next;
    }
    ListNode  res =temp.next;
    temp.next =null;
    return res;
}

[atom-set]

思路

• step1: 先对链表进行翻转，同时记录链表长度(len)，同时记录最后一个节点的前驱节点(tailPrev) 和头节点 newHead
• step2: 对 k 进行裁剪，只需要移动 k % len 次
• step3: 每次移动时候，进行操作

// 暂存头结点
var headNextNode = newHead.next;
// 最后一个节点的前驱节点后移
tailPrev = tailPrev.next;
// 更新最后一个节点为暂存的头结点
tailPrev.next = newHead;
// 切断链接
tailPrev.next.next = null;
// 更新头结点
newHead = headNextNode;

• step4: 再次进行翻转，输出

代码

/**
 * 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 || (head && !head.next) || k === 0) {
    return head;
  }

  var newHead = null;
  var tailPrev = null;
  var len = 0;

  // 头节点
  while (head) {
    //  1->2->3->4->5->NULL
    const nextNode = head.next;

    // 头插法。从头往后插入
    head.next = newHead;
    newHead = head;

    head = nextNode;

    if (newHead && newHead.next && !newHead.next.next) {
      tailPrev = newHead;
    }
    len++;
  }

  for (var i = 0; i < k % len; i++) {
    var headNextNode = newHead.next;
    tailPrev = tailPrev.next;
    tailPrev.next = newHead;
    tailPrev.next.next = null;
    newHead = headNextNode;
  }

  while (newHead) {
    const nextNode = newHead.next;
    // 头插法。从头往后插入
    newHead.next = head;
    head = newHead;

    newHead = nextNode;
  }

  return head;
};

复杂度分析

对链表进行遍历，时间复杂度是 O(N)

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

[zin-next]

var rotateRight = function(head, k) {
    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;
    }

    tail.next = head;

    let newTail = head;
    for (let i = 0; i < length - k - 1; i++) {
        newTail = newTail.next;
    }

    let newHead = newTail.next;

    newTail.next = null;

    return newHead;
};

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

[Alexzhang-Mini]

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
        tail = head
        while tail.next:
            tail = tail.next
            length += 1

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

        tail.next = head

        new_head_prev = head
        for i in range(length - k - 1):
            new_head_prev = new_head_prev.next

        new_head = new_head_prev.next
        new_head_prev.next = None

        return new_head

[lxy1108]

思路

首先遍历一遍链表，得到链表的长度和链表的尾节点； 再次从头遍历链表，指针停在旋转后链表的尾节点，然后进行链表后续节点的重新分配

python3代码

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

复杂度分析

时间复杂度O(n)，因为需要从头遍历链表 空间复杂度O(1)

[YANGLimbo]

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        //我的思路，先走到头看看有多长（应该没有环吧？）记为n
        // 然后获取k % n，其中一个走n-k%n步，让它屁股后面断开，末尾连这里。最后返回那一步后面的指针
        if(head == nullptr){
            return nullptr;
        }

        ListNode* lastNode = head;
        int n = 1;
        while(lastNode->next!= nullptr){
            lastNode = lastNode->next;
            n++;
        }
        ListNode* node = head;
        for(int i = 1; i < n-k%n; i++){
            node = node->next;
        }
        if(node->next == nullptr){
            //刚好转了整圈数
            return head;
        }else{
            ListNode* newHead = node->next;
            node->next = nullptr;
            lastNode->next = head;
            return newHead;
        }

    }
};

[pandapls]

var rotateRight = function(head, k) {
    if (!head || !head.next || k === 0) {
        return head
    }
    let len = 1;
    let cur = head;
    while(cur.next) {
        cur = cur.next;
        len++
    }
    let n = len - ( k % len );
    cur.next = head;
    if (n === len) {
        cur.next = null;
        return head
    };

    cur.next = head;
    while (n > 0) {
        cur = cur.next;
        n--;
    }

    const res = cur.next;
    cur.next = null;

  return res;
};

复杂度分析

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