azl397985856 commented 1 year ago

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

Meisgithub commented 1 year ago

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        ListNode* p = head;
        if (p == nullptr)
        {
            return nullptr;
        }
        int n = 1;
        while (p->next)
        {
            p = p->next;
            n++;
        }
        p->next = head;
        k = k % n;
        p = head;
        int i = 1;
        while (i < n - k)
        {
            p = p->next;
            i++;
        }
        ListNode* newHead = p->next;
        p->next = nullptr;
        return newHead;
    }
};

for123s commented 1 year ago

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(head==NULL)
            return NULL;
        ListNode* temp = head;
        int len = 1;
        while(temp->next!=NULL)
        {    
            temp = temp->next;
            ++len;
        }
        temp->next = head;
        int step = len - k%len;
        while(--step)
            head = head->next;
        temp = head->next;
        head->next = NULL;
        return temp;
    }
};

Manwzy commented 1 year ago

/**

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(k===0){ return head } let stash = [] let cur = head

while(cur && k>0){ stash.push(cur.val) cur = cur.next k-- } let i = 0

if(!cur && !k){ return head }

if(!cur){ k%=stash.length cur = head while(cur){ cur.val = stash[(i+stash.length - k)%stash.length] cur = cur.next i++ } }else{ while(cur){ stash.push(cur.val) cur.val = stash[i] cur = cur.next i++ } cur = head while(i<stash.length){ cur.val = stash[i] cur = cur.next i++ } }

return head };

snmyj commented 1 year ago

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        ListNode* p=head,newhead;
        int length=0,cnt=0;
        while(p!=nullptr){
            length++;
            p=p->next;
        }
        p=head;
        while(p!=nullptr){
            cnt++;
            p=p->next;
            if(cnt==length-k){
                newhead=p->next;
                p->next=nullptr;

            }
            if(cnt==length) {
                p->next=head;
                break;
            }
        }
        return newhead;
    }
};

T:O(n); S:O(1);

yfu6 commented 1 year ago

Use the n - k % n - 1 to calculate the new ring tail with the old ring head

class Solution:
def rotateRight(self, head: 'ListNode', k: 'int') -> 'ListNode':
    if not head:
        return None
    if not head.next:
        return head

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

    new_tail = head
    for i in range(n - k % n - 1):
        new_tail = new_tail.next
    new_head = new_tail.next

    new_tail.next = None

    return new_head

3.O(n) O(1)

LIMBO42 commented 1 year ago

/**
 * 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) return head;
        int size = 0;
        ListNode* cur = head;
        while(cur) {
            cur = cur->next;
            size++;
        }
        if(size == 0) return head;
        int num = k % size;
        if(num == 0) return head;
        ListNode* slow = head;
        ListNode* fast = head;
        while(num) {
            num--;
            fast = fast->next;
        }
        while(fast->next) {
            slow = slow->next;
            fast = fast->next;
        }
        ListNode* ans = slow->next;
        slow->next = nullptr;
        fast->next = head;
        return ans;

    }
};

954545647 commented 1 year ago

思路

暴力解法：先计算链表长度

代码

/**
 * 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.next) return head;
  let length = 0;
  let temp = head;
  // 计算链表长度
  while (temp) {
    temp = temp.next;
    ++length;
  }
  // 优化旋转个数
  k = k % length;
  if (k === 0) return head;
  let slow = (fast = head);
  // 快慢指针，找到倒数第K个元素
  while (fast.next) {
    if (k-- <= 0) {
      slow = slow.next;
    }
    fast = fast.next;
  }
  fast.next = head;
  // 第K+1个元素先暂存
  let res = slow.next;
  slow.next = null;
  return res;
};

复杂度分析

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

jackgaoyuan commented 1 year ago

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func rotateRight(head *ListNode, k int) *ListNode {
    // 边界守护
    if head == nil {
        return head
    }
    // 存储节点头，节点头的Next都是nil，避免处理环
    headList := []*ListNode{}
    // 节点list的长度
    n := 0
    // 节点的指针
    p := head
    // 计数器，计算处理结束
    count := 1
    // 应该处理的长度，因为当处理的次数与总长度相等时，会出现周期性的循环，所以应处理次数为 k%n，只求余数即可
    totalCount := 0

    // 将节点放入list
    for p != nil {
        headList = append(headList, p)
        pNext := p.Next
        p.Next = nil
        p = pNext
        n++
    }

    totalCount = k % n
    p = head

    // 先将数组进行选装，不处理节点
    for count <= totalCount {
        headList = append(headList[n-1:], headList[0:n-1]...)
        count++
    }

    // 连接处理的节点
    for i := 0; i < n; i++ {
        if i == n-1 {
            headList[i].Next = nil
            continue
        }
        headList[i].Next = headList[i+1]
    }

    head = headList[0]

    return head
}

bookyue commented 1 year ago

TC: O(n)
SC: O(1)

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

        int n = 1;
        var cur = head;
        while (cur.next != null) {
            cur = cur.next;
            n++;
        }

        k %= n;
        if (k == 0) return head;

        cur.next = head;
        k = n - k - 1;

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

        var newHead = head.next;
        head.next = null;
        return newHead;
    }

kofzhang commented 1 year ago

思路

找出链表长度取一下模，然后向后走最后记得断开链表

复杂度

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

代码

# 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 not head or not head.next:
            return head
        dummy = head
        l = 1
        while head.next:
            head = head.next
            l += 1

        k = (l - k % l)%l
        if k == 0 :
            return dummy
        head.next = dummy
        head = dummy
        while k > 1:   
            head = head.next
            k -= 1
        res = head.next
        head.next = None
        return res

duke-github commented 1 year ago

思路

成环再拆环

复杂度

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

代码

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

dujt-X commented 1 year ago

题目

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

将链表旋转k次，其中k是非负整数，即将链表的最后k个节点移动到链表的头部。

思路分析

需要找到链表中的倒数第k个节点，并将链表从这个节点处分成两个部分，然后将第二部分连接到链表的头部。

首先遍历一次链表，以确定链表的长度。
如果k大于链表的长度，将k对链表的长度取模，以确保它不大于链表的长度。
定义两个指针：快指针和慢指针，都指向链表的头部。快指针向前移动k步，然后慢指针和快指针同时向前移动，直到快指针到达链表的尾部。
将第二部分链表的尾部与第一部分链表的头部相连接。

将第二部分链表的头部作为新的头节点返回。

代码实现

Golang

func rotateRight(head *ListNode, k int) *ListNode {
// 特殊情况：链表为空或只有一个节点
if head == nil || head.Next == nil {
    return head
}

// 计算链表的长度
n := 1
curr := head
for curr.Next != nil {
    n++
    curr = curr.Next
}

// 如果k大于链表的长度，将k对链表的长度取模
k = k % n

// 特殊情况：k等于0，即不需要旋转
if k == 0 {
    return head
}

// 定义快指针和慢指针
fast := head
slow := head

// 快指针向前移动k步
for i := 0; i < k; i++ {
    fast = fast.Next
}

// 移动慢指针和快指针，直到快指针到达链表的尾部
for fast.Next != nil {
    slow = slow.Next
    fast = fast.Next
}

// 将第二部分链表的尾部与第一部分链表的头部相连接
new_head := slow.Next
slow

复杂度分析

时间复杂度：O(n)，其中n是链表的长度。需要遍历一次链表来计算链表的长度，遍历一次链表来找到倒数第k个节点，所以时间复杂度是O(n)。

空间复杂度：O(1)，只使用了常数级别的额外空间。

dorapocket commented 1 year ago

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(head==nullptr) return head;
        vector<ListNode*> l;
        ListNode* p=head;
        while(p!=nullptr) { l.emplace_back(p); p=p->next;}
        k=k%l.size();
        if(k==0) return head;
        l[l.size()-1]->next = l[0];
        l[l.size()-k-1]->next = nullptr;
        return l[l.size()-k];
    }
};

NorthSeacoder commented 1 year ago

代码 (环)

/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var rotateRight = function(head, k) {
    if (!head || !head.next || k === 0) return head;
    let point = head;
    let length = 1;
    while (point.next) {
        length++;
        point = point.next;
    }
    if (k % length === 0) return head;

    let n = length - (k % length);
    //构建环
    point.next = head;
    //找到新链表头结点的前驱节点:n+k = length
    while (n > 0) {
        point = point.next;
        n--;
    }
    let newHead = point.next;
    point.next = null;
    return newHead;
};

复杂度

TC: O(n)
SC:O(1)

代码(双指针)

var rotateRight = function(head, k) {
    if (!head || !head.next || k === 0) return head;
    let point = head;
    let length = 1;
    while (point.next) {
        length++;
        point = point.next;
    }
    if (k % length === 0) return head;

    let n = k % length;

    let fast = head;
    let slow = head;
    //先移动 fast
    while (n > 0) {
        fast = fast.next;
        n--;
    }
    //同步移动,最终 slow 为新链表头结点前驱节点
    while (fast.next) {
        fast = fast.next;
        slow = slow.next;
    }
    fast.next = head;
    head = slow.next;
    slow.next = null;
    return head;
};

复杂度

TC: O(n)
SC:O(1)

csthaha commented 1 year ago

复杂度：

时间复杂度：O(n)

空间复杂度：O(1)

代码：

/**
* 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 (k === 0 || !head || !head.next) {
    return head;
}
let cur = head;
let count = 0;
while(cur) {
    count++;
    if(!cur.next) {
        // 成环
        cur.next = head;
        break;
    } else {
        cur = cur.next;
    }
}
let remain = k % count; //求余数

// head 需要移动 remain 下， 成环后（cur.next = head） ， cur 需要移动 add 下。
// cur.next 为 头节点。然后断开环。
let add = count - remain;

if(add === count) {
    cur.next = null;
    return head;
}

let res = null;
while (add) {
    cur = cur.next;
    add--;
}

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

return res;
};

JiangyanLiNEU commented 1 year ago

Idea

get the length of the linked list
k = k%length

break and rebuild the link

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

    k = k%length
    if k == 0:
        return head
    slow = fast = head
    for _ in range(length-k-1):
        fast = fast.next
    end = fast
    newHead = fast = fast.next
    end.next = None
    while fast and fast.next:
        fast = fast.next
    fast.next = slow
    return newHead

Time Complexity = O(N)
Space Complexity = O(1)

Elsa-zhang commented 1 year ago

# 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 not head:
            return 

        cur = head
        length = 0
        while cur:
            cur = cur.next
            length+=1
        rotate_length = k%length
        l = length - rotate_length

        if l==length:
            return head

        node1 = head
        temp1 = node1
        while l-1:
            node1 = node1.next
            l-=1
        node2 = node1.next
        node1.next = None

        temp2 = node2
        while node2.next:
            node2=node2.next
        node2.next = temp1

        return temp2

hatoriMain commented 1 year ago

题目名

链接：https://leetcode.com/problems/rotate-list/description/

解法思路1:

先遍历链表一遍，此时记录链表本身的长度。并且让链表成环。

让k = k % len。此时让指针再走len - k 格。就可以走到旋转链表的链表的tail节点。记录这个节点的next节点。让他把tail的next节点变为null断尾。

注意要点：

复杂度：

时间：$O(n)$

空间：$O(1)$

第一次自己写的代码：

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

        while(p.next != null){
            p = p.next;
            len++;
        }
        p.next = head;
        k = k % len;
        k = len - k;
        for(int i = 0; i < k; i++) {
            p = p.next;
        }
        ListNode res = p.next;
        p.next =null;
        return res;
    }
}

Yufanzh commented 1 year ago

# 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]:
        # this has to split the linked list at k places --> consider slow-fast pointers
        # edge case for linked list
        if not head or not head.next or k == 0:
            return head
        # based on constraint, k is not necessarily smaller than length of node, so there can be multiples, we want to get the mod to be more efficient
        # step 1, get the length of the linked list first
        length = 1
        p0 = head
        while p0.next:
            p0 = p0.next
            length += 1
        k = k % length

        # now use fast slow pointers to find the k places
        p_slow = head
        p_fast = head
        while k > 0:
            p_fast = p_fast.next
            k -= 1
        while p_fast.next:
            p_fast = p_fast.next
            p_slow = p_slow.next
        # now we reach the flip location
        p_fast.next = head
        res = p_slow.next
        p_slow.next = None
        return res

Leonalhq commented 1 year ago

class Solution(object):
    def rotateRight(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        if not head or k == 0:
            return head

        act = head
        l = 1
        while act.next:
            act = act.next
            l +=1
        act.next = head

        a_k = k%l
        a_l = l - a_k - 1

        # Find the new head
        new_tail = head
        for i in range(a_l):
            new_tail = new_tail.next

        new_head = new_tail.next
        # print(a_l, new_head)
        # cut from previous end
        new_tail.next = None

        return new_head

suukii commented 1 year ago

Time: $O(N)$

Space: $O(1)$

function rotateRight(head: ListNode | null, k: number): ListNode | null {
if (!head) return null;

let len = 1;
let p = head;

while (p.next) {
    p = p.next;
    len++;
}

p.next = head;
k %= len;
k = len - k;

while (k--) {
    p = p.next;
}

const rotatedHead = p.next;
p.next = null;
return rotatedHead;
};

Abby-xu commented 1 year ago

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

      #check the length
        lastNode, length = head, 1
        while lastNode.next:
            lastNode = lastNode.next
            length += 1

        # check the number of rotation
        k = k % length

      # setlast node point to the first node
        lastNode.next = head

      #traverse until (length - k) node
        temp = head
        for i in range(length - k - 1): temp = temp.next

      #disconnect the first and last node
        out = temp.next
        temp.next = None

        return out

Fuku-L commented 1 year ago

思路

分析测试案例可知，将链表的每一位都移动k个位置，相当于将链表的后续k个节点连到head。
使用两个指针 p1 和 p2， p2 先走k步（若p2走到尾节点，说明k>size，可以优化k=(k%size)+size，减少循环走次数。）
p1 和 p2 一起走，直到p2到达尾节点。将p2.next连到head，将head指向 p1.next 作为新的头，将p1.next置空。
返回head。

代码

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

        ListNode p1 = head;
        ListNode p2 = head;
        int size = 1;
        for(int i = 0; i < k; i++){
            if(p2.next!=null){
                p2 = p2.next;
                size++;
            } else {
                p2 = head;
                k = (k % size) + size;
            }
        }

        while(p2.next!=null){
            p2 = p2.next;
            p1 = p1.next;
        }

        p2.next = head;
        head = p1.next;
        p1.next = null;

        return head;
    }
}
/**
 * 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; }
 * }
 */

复杂度分析

时间复杂度：O(N)，其中 N 为数组长度。
空间复杂度：O(N)

xb798298436 commented 1 year ago

class Solution { public ListNode rotateRight(ListNode head, int k) { int len = 1; ListNode p = head; while(p.next != null){ p = p.next; len++; } p.next = head; k = k % len; k = len - k; for(int i = 0; i < k; i++) { p = p.next; } ListNode res = p.next; p.next =null; return res; } }

wangqianqian202301 commented 1 year ago

思路

把列表做成一个环，走length - k步，就是新的头结点

代码

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

        step = length - k
        temp = head
        while step > 1:
            temp = temp.next
            step = step - 1
        head = temp.next
        temp.next = None

        return head

复杂度

O(n)

jmaStella commented 1 year ago

思路

fast 和slow两个pointer。先找到整个list长度N。fast走 k%N步，找到新的head，修改 edge case：empty list，k=0 or k%N=0

代码

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

        int len = 0;
        while(fast != null){
            fast = fast.next;
            len++;
        }
        fast = head;
        if(k==0 || k%len == 0){
            return head;
        }
        for(int i=0; i<k%len; i++){
            fast = fast.next;
        }
        while(fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }

        ListNode temp = slow.next;
        slow.next = null;
        fast.next = head;

        return temp; 

    }
}

复杂度

时间：O(N) 空间：O(1)

AstrKing commented 1 year ago

思路

1、首先我们先确认一个概念，当整体向右边移动1个位置，相当于把链表的最后1位移动到head前面，移动2个位置，就是把链表的最后两位移动到head前面
2、如果说链表的整体长度为k，你移动k，相当于没有移动(把链表当成一个环来处理)
3、所以我们的移动，只需要考虑K对链表长度的求余即可
4、那么后续问题，就可以转化为查询链表上面倒数第几个元素了，这样就十分方便了

代码

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(head == null || head.next == null) return head;
        int count = 0;
        ListNode now = head;
        while(now != null){
            now = now.next;
            count++;
        }
        k = k % count;
        ListNode slow = head, fast = head;
        while(fast.next != null){
            if(k-- <= 0){
                slow = slow.next;
            }
            fast = fast.next;
        }
        fast.next = head;
        ListNode res = slow.next;
        slow.next = null;
        return res;
    }
}

复杂度分析

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

hshen202108 commented 1 year ago

题目地址(61. 旋转链表)

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

题目描述

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

 

示例 1：

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

示例 2：

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

 

提示：

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

前置知识

公司

暂无

思路

关键点

代码

语言支持：Java

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

复杂度分析

令 n 为数组长度。

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

yingchehu commented 1 year ago

思路

要 rotate linked list，就先找到對的位置，拆掉重新接起來用快慢指針相隔 k，接著快指針走到最後一個 node 的時候慢指針便為在新的 linked list 的最後一個 node 最後就尾接到頭，新的 head 在慢指針的下個節點，再把慢指針指到的 node 斷開

Code

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

        p = head
        length = 1
        while p.next:
            length += 1
            p = p.next

        k = k % length
        fast = slow = head
        while fast.next:
            fast = fast.next
            if k > 0:
                k -= 1
            else:
                slow = slow.next

        fast.next = head
        head = slow.next
        slow.next = None
        return head

複雜度

Time: O(N) Space: 未使用額外空間 O(1)

zcytm3000 commented 1 year ago

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

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

    if (add := n - k % n) == n:
        return head

    cur.next = head
    while add:
        cur = cur.next
        add -= 1

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

huifeng248 commented 1 year ago


# make a circle and move along in k step, return the elements after the k.
# there is still edge cases for this one, I will update it tmr to close the cases. 
# 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]:
        # need to walk through the total linked list and get the total number of node
        # total - k is the one that need to point to none, and the second half till end need to point to head 
        # return the second half head.
        if k == 0:
            return head
        if head is None:
            return None
        if head.next is None:
            return head
        arr = [head.val]
        current = head 
        while current.next:
            arr.append(current.next.val)
            current = current.next
        current.next = head
        total_len = len(arr)

        move_step = k % total_len
        print("move_step", move_step)
        if move_step == 0:
            return head

        new_tail = head
        for i in range(total_len - move_step -1):
            new_tail = new_tail.next
            print("i", i)
        print(new_tail.val)

        answer = new_tail.next
        new_tail.next = None
        return answer

Hughlin07 commented 1 year ago

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

    ListNode curNode = head;
    int length = 1;
    while(curNode.next != null){    
        curNode = curNode.next;
        length ++;
    }

    ListNode tailNode = curNode;
    curNode.next = head;
    curNode = head;

    int loopCount = length - (k%length);
    for(int i = 0; i < loopCount; i++){
        curNode = curNode.next;
        tailNode = tailNode.next;
    }
    tailNode.next = null;
    return curNode;
}

}

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

Zoeyzyzyzy commented 1 year ago

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

chanceyliu commented 1 year ago

代码

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val?: number, next?: ListNode | null) {
    this.val = val === undefined ? 0 : val;
    this.next = next === undefined ? null : next;
  }
}

function rotateRight(head: ListNode | null, k: number): ListNode | null {
  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 as ListNode;
    add--;
  }

  const ret = cur.next;
  cur.next = null;
  return ret;
}

复杂度分析

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

Horace7 commented 1 year ago

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

    let n = len - (k % len);
    point.next = head;
    while (n > 0) {
        point = point.next;
        n--;
    }
    let res = point.next;
    point.next = null;
    return res;
};

franciszq commented 1 year ago

思路

就是截断链表，重新换个链表头，并且原来的尾巴指向原来的表头。步骤如下

先计算链表的长度size
如果k大于size的话，会有重复，所以用k%size，得到的值，就是移动的距离move_size
找到4个节点：原来的表头，原来的表尾，原来的size-move_size-1的节点（cut_node），size-move_size的节点（新的表头）。
表尾next指向表头，size-move_size-1；cut_node的next指向null。返回size-move_size的节点

注意点

if (head == nullptr || head->next == nullptr || k == 0)的话，直接返回head
k%size == 0的话，不旋转

代码

class Solution
{
public:
    ListNode* rotateRight(ListNode* head, int k)
    {
        if (head == nullptr || head->next == nullptr || k == 0) {
            return head;
        }
        ListNode* first_node = head;
        int list_size = 1;
        while (head->next != nullptr) {
            head = head->next;
            list_size++;
        }
        ListNode* last_node = head;
        int rotate_size = k % list_size;
        if (rotate_size == 0) {
            return first_node;
        }
        ListNode* cut_node = first_node;
        for (int i = 0; i < list_size - rotate_size - 1; ++i) {
            cut_node = cut_node->next;
        }
        head = cut_node->next;
        last_node->next = first_node;
        cut_node->next = nullptr;
        return head;

    }
};

复杂度

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

kangliqi1 commented 1 year ago

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

zhangyong-hub commented 1 year ago

思路

采用递归，先把链表形成环，记录头结点

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(!head || head->next==nullptr || k==0)
            return head;
        temphead=head;
        return helper(head,k);    
    }
        ListNode *temphead;//记录头结点 
        int L = 0;//反转几次
        int nums =0;//记录长短
    ListNode* helper(ListNode* head, int k){
        if(head==nullptr)
            return head;
        nums++;
        if(helper(head->next,k)==nullptr){
            L= k%nums;
            head->next = temphead;//形成环
        }
        if(L==0){
            temphead = head->next;
            head->next = nullptr;
        }
        L--;
        return temphead;

    }
};

Quieter2018 commented 1 year ago

思路： 将尾部向前数第K个元素作为头，原来的头接到原来的尾上，其实就是找倒数第k个元素。

代码：

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(head == NULL || head->next == NULL|| k == 0){
            return head;
        }

        //计算链表长度
        int length = 1;
        ListNode *p = head;
        while(p->next!=NULL){
            length++;
            p = p->next;
        }

        //若右移k == n*length,相当于链表不用动
        k= k % length;
        if(k==0){
            return head;
        }

        //快慢指针,找到倒数k个值
        ListNode *fast = head;
        ListNode *slow = head;
        int i = k;
        while(i>0){
            fast = fast->next;
            i--;
        }

        while(fast->next!= NULL){
            slow = slow->next;
            fast = fast->next;
        }

        ListNode *new_head =  slow->next; 
        slow->next = NULL;
        fast->next = head;

        return new_head;

    }
};

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

harperz24 commented 1 year ago

# 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 not head or not head.next: 
            return head

        # in order to make it a circular linked list and count the length,
        # iterate to find the tail node and link the tail.next to head
        length = 1
        cur = head
        while cur.next:
            cur = cur.next
            length += 1
        cur.next = head

        newTail = head
        for i in range(length - k % length - 1):
            newTail = newTail.next
        newHead = newTail.next
        newTail.next = None

        return newHead

        # time: O(N)
        # space: O(1)

texamc2 commented 1 year ago

// 旋转链表函数
func rotateRight(head *ListNode, k int) *ListNode {
    // 如果链表为空或只有一个结点或k为0，直接返回head
    if head == nil || head.Next == nil || k == 0 {
        return head
    }
    // 定义变量n表示链表长度，tail表示尾结点
    n := 1
    tail := head
    // 遍历链表，更新n和tail
    for tail.Next != nil {
        n++
        tail = tail.Next
    }
    // 计算k对n取模，得到实际需要移动的步数m
    m := k % n
    // 如果m为0，说明不需要旋转，直接返回head
    if m == 0 {
        return head
    }
    // 定义变量cur表示当前结点，初始化为head
    cur := head
    // 从head开始向后走n-m-1步，找到新的尾结点newTail和新的头结点newHead 
    for i := 0; i < n - m - 1; i++ {
        cur = cur.Next 
    }
    newTail := cur 
    newHead := cur.Next 
    // 将newTail的next指针置空，将tail的next指针指向head，完成旋转 
    newTail.Next = nil 
    tail.Next = head 
    // 返回newHead作为结果 
    return newHead 
}

X1AOX1A commented 1 year ago

0061. 旋转链表

题目

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

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

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

思路

通过计算链表长度，可以将缩小 k
1. 将 old tail node 的 next 设置为 old head
2. 读取目标两个节点【只有两个节点，因此不必使用 queue】
3. 第一个节点的 next 设置为 None，即为 new tail node
4. 第二个节点为 new head

代码

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

        # 0. Calculate len and reduce k
        Len, cur = 0, head
        while cur:
            Len += 1
            prev, cur = cur, cur.next            
        k %= Len

        # 1. Link old tail node to head
        prev.next = head

        # 2. Find target nodes      
        new_tail, new_head = None, None
        cur_idx, cur = 0, head
        while cur_idx <= Len-k:
            new_tail, new_head = new_head, cur            
            cur_idx, cur = cur_idx+1, cur.next
        # 2.1 Link new tail node to None
        new_tail.next = None
        # 3.2 Return new head
        return new_head

时间复杂度：O(N)，N 为链表长度
空间复杂度：O(1)
时间 36 ms 击败 86.77%
内存 14.8 MB 击败 95.47%

Elon-Lau commented 1 year ago

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

CruiseYuGH commented 1 year ago

关键点

代码

语言支持：Python3

Python3 Code:


# 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 head:
            slow , fast = head ,head
            tmp = head
            leng = 0
            while tmp:
                tmp = tmp.next
                leng +=1
            k = k%leng
            while k:
                fast = fast.next
                k -=1
            while fast.next:
                slow = slow.next
                fast = fast.next
            if slow.next:
                tmp = slow.next
            else:
                return head
            slow.next = None
            fast.next = head
            return tmp

复杂度分析

令 n 为数组长度。

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

JingYuZhou123 commented 1 year ago

/**
 * @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--;
    }

    let res = cur.next;
    cur.next = null;
    return res;
}

luckyoneday commented 1 year ago

代码

var rotateRight = function (head, k) {
  if (!(head && head.next)) return head;
  if (k === 0) return head;
  let node = head;
  const node4 = head;
  let len = 1;
  while (node.next) {
    len++;
    node = node.next
  }

    let newLen = k % len === 0 ? 0 : Math.abs(len - k % len);
  if (newLen === 0) return node4;
  while (newLen > 1) {
    newLen--;
    head = head.next;
  }

  let node3 = head.next;
  head.next = null;
  const node5 = node3;

  while (node3 && node3.next) {
    node3 = node3.next;
  }
  if (node3) {
    node3.next = node4;
  }

  return node5;
};

huizsh commented 1 year ago

func rotateRight(head *ListNode, k int) *ListNode {
    if head == nil || k == 0 {
        return head
    }

    p1, p2 := head, head
    count := 1
    i := 0
    for i < k {
        if p2.Next != nil {
            count++
            p2 = p2.Next
        } else {
            k = k % count
            i = -1
            p2 = head
        }
        i++
    }

    for p2.Next != nil {
        p1 = p1.Next
        p2 = p2.Next
    }

    tmp := p1.Next
    if tmp != nil {
        p1.Next = nil
        p2.Next = head
        return tmp
    }
    return head
}

RestlessBreeze commented 1 year ago

code

/**
 * 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) return nullptr;
        int length = 1;
        ListNode* H = head;
        while (H -> next)
        {
            H = H -> next;
            length++;
        }  
        H -> next = head;
        k = length - k % length;
        while (k > 1)
        {
            head = head -> next;
            k--;
        }
        H = head;
        head = H -> next;
        H -> next = nullptr;
        return head;
    }
};

zpbc007 commented 1 year ago

思路

快慢指针，先让头指针移动 K 次，然后头尾指针同时移动，直到头指针移动到链表尾部。此时让头节点指向链表的头，尾结点的下个节点作为新链表的头结点，并将尾结点清空。

代码

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

    let first: ListNode | null = head
    let last: ListNode | null = head
    let step = 0

    // 第一个指针先移动 K 
    let index = 0
    while (index < k) {
        first = move2Next({cur: first, head})

        index++
    }

    while (first.next !== null) {
        first = move2Next({cur: first, head})
        last = move2Next({cur: last, head})

        step++
    }

    first.next = head
    const newHead = last!.next
    last!.next = null

    return newHead
};

/**
 * 考虑循环移动的场景
 */
function move2Next({ cur, head }: { cur: ListNode, head: ListNode }) {
    if (cur.next) {
        return cur.next
    }

    return head
}

复杂度分析

时间复杂度：整个链表遍历一次 O(N)
空间复杂度：无额外开销 O(1)

WL678 commented 1 year ago

思路：

如果给的是循环链表，那么只需要考虑移动head指针就可以了，但题目中给出的是单链表，所以需要先遍历整个链表，得到链表的长度，同时将链表首尾相连，然后根据输入的k移动head，之后再断掉head前面的连接即可。

整体的思路是这样，但是有两种特殊情况，需要考虑，

k是count的倍数，此时，head不需要挪动，之间返回即可。

k大于count，此时需要对count - k取模，但此时得到的结果是负数，因此还需要加上一个count。

代码：C++

/**
 * 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 count = 1;
        ListNode* temp = head;
        //得到链表的总长度
        while(head->next != nullptr) {
            count++;
            head = head->next;
        }
        if( k % count !=0){
        //首尾相连
        head -> next = temp;
        head = temp;
        int rotTimes = 0;
        if(count < k)
            rotTimes = (count - k) % count + count; //k mod count,取正数
        else 
            rotTimes = count - k;
        for(int i = 1; i < rotTimes ; i++){
            head = head -> next;
        }
        ListNode* temp2 = head -> next;
        head -> next = nullptr;
        head = temp2;
        }
        else{
            //k为count整数倍，不需要移动
            head = temp;
        }
        return head;
    }
};

复杂度分析：

时间复杂度：O(max(n,k))

空间复杂度：O(1)

leetcode-pp / 91alg-10-daily-check

【Day 7 】2023-02-20 - 61. 旋转链表 #10

61. 旋转链表

入选理由

题目地址

前置知识

题目描述

思路

代码

思路

复杂度

代码

思路

复杂度

代码

题目

思路分析

代码实现

复杂度分析

代码 (环)

复杂度

代码(双指针)

复杂度

复杂度：

代码：

Idea

题目名

解法思路1:

注意要点：

复杂度：

第一次自己写的代码：

思路

代码

思路

代码

复杂度

思路

代码

复杂度

思路

代码

复杂度分析

题目地址(61. 旋转链表)

题目描述

前置知识

公司

思路

关键点

代码

思路

Code

複雜度

代码

思路

注意点

代码

复杂度

思路

0061. 旋转链表

题目

思路

代码

关键点

代码

代码

code

思路

代码

复杂度分析