azl397985856 commented 2 years 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

yan0327 commented 2 years ago

思路：本题是由倒数第N个链表和环形链表相结合。实现链表循环的关键是，将尾节点与头节点接起来。由于题目需要求倒数第k个节点，因此需要先遍历一遍链表得到sum【设head = 1，条件为head.Next != nil】因此由倒数第k个节点，可以得到整数第sum个节点 sun -= k%sum 最后，找到这个点，先将head.Next作为输出保留，其次将head.Next =nil 断开链表【注意边界条件的判断，如k=0和输入链表为nil】

func rotateRight(head *ListNode, k int) *ListNode {
    if head == nil||k==0{
        return head
    }
    pre := head
    sum := 1
    for pre.Next != nil{
        pre = pre.Next
        sum++
    }
    sum -= k %sum
    pre.Next = head
    for i:=0;i<sum;i++{
        pre = pre.Next
    }
    out := pre.Next
    pre.Next = nil
    return out
}

时间复杂度：O（n）空间复杂度：O（1）

CodeWithIris commented 2 years ago

Note

Special case judgment: 1.k == 0; 2.head == nullptr; 3. head->next == nullptr(only 1 element in the linked list). In all 3 cases above, return head.
Traverse the list and record the length of the linked list. Get the breakpoint of the linked list / the end of the answer list through this formula:
Breakpoint Index = Length of the linked list - k % Length of the linked list.
Connect the tail of the original linked list to the head, break at the breakpoint and return the new head of the list.

Solution (C++)


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

Complexity

T: O(n), traverse the entire list at most twice
S: O(1), only constant space

sujit197 commented 2 years ago

思路

首先得到链表长度length，将尾节点与头节点相连，在移动length-k%length个节点后将链表断开；

代码（JAVA）

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(head == null){
            return head;
        }
        ListNode temp = head;
        int length = 1;
        while(temp.next!=null){
            length++;
            temp = temp.next;
        }
        temp.next = head;

        for (int i = 0;i<length-k%length;i++){
            temp = temp.next;
        }
        ListNode res = temp.next;
        temp.next = null;
        return res;

    }
}

复杂度

时间复杂度：需要遍历链表O（N）空间复杂度：无需额外空间 O（1）

Grendelta commented 2 years ago

思路

先计算单项链的长度n，并将链尾与链首相连，最后根据n和k的大小关系切断链表

代码

class Solution(object): def rotateRight(self, head, k): """ :type head: ListNode :type k: int :rtype: 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

    time = n - k % n 
    if time == n:
        return head

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

    res = cur.next
    cur.next = None
    return res

复杂度

时间复杂度 O(N)

空间复杂度 O(1)

charlestang commented 2 years ago

思路

计算长度，然后取模，然后计算新的头部节点位置。

可以把链表串起来，然后一起移动头尾指针，这样找到新头尾后截断。

代码

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

        cnt = 1
        tail = head
        while tail.next:
            cnt += 1
            tail = tail.next

        # make a circle
        tail.next = head

        move = cnt - (k % cnt)
        while move > 0:
            head = head.next
            tail = tail.next
            move -= 1

        tail.next = None
        return head

时间复杂度 O(n)

zjsuper commented 2 years ago

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

        if cur.next == None:
            cur.next = head
            break
        cur = cur.next

    pos = k% count 
    print(pos)
    breakpoint = count - pos
    if breakpoint == 0:
        return head
    else:
        ans = cur
        cur = cur.next 
        for i in range(breakpoint-1):
            cur = cur.next 
        nextn = cur.next
        cur.next = None
        return nextn

zwmanman commented 2 years ago

思路

Calculate length of the list
find tail and last k+1 node
connect tail and head
cut k+1 node with next

代码

# 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):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """

        if not head or not head.next or k == 0:
            return head

        length = 1

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

        k = k % length

        if k == 0:
            return head

        fast = head
        slow = head

        while fast.next:
            if k <= 0:
                slow = slow.next
            k -= 1
            fast = fast.next

        temp = slow.next
        slow.next = None
        fast.next = head

        return temp

复杂度分析

时间复杂度：O(N)，其中 N 为链表长度。
空间复杂度：O(1)

ginnydyy commented 2 years ago

Problem

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

Note

check the size and actual k before rotating
use newHead/newTail/oldTail to point to the important nodes

Solution

/**
 * 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) {
        // get the size of the list and find the oldTail
        // size % k => actual k
        // if actual k is 0, return head
        // move from head with size - actual k -1 steps, find the newTail
        // new head is newTail.next
        // link oldTail with old head
        // cut the newTail
        // return new head

        // T: O(n) n is the size of the list
        // S: O(1) no extra space is required

        if(head == null || head.next == null || k <= 0){
            return head;
        }

        int size = 1;
        ListNode oldTail = head;
        while(oldTail != null && oldTail.next != null){
            size++;
            oldTail = oldTail.next;
        }

        int actualK = k % size;
        if(actualK == 0){
            return head;
        }

        ListNode newTail = head;
        for(int i = 0; i < size - actualK - 1; i++){
            newTail = newTail.next;
        }

        ListNode newHead = newTail.next;

        oldTail.next = head;
        newTail.next = null;
        return newHead;
    }
}

Complexity

T: O(n) n is the size of the list
S: O(1) no extra space is required

JudyZhou95 commented 2 years ago

思路

rotate可以把链表想象成一个环，计算出需要转的steps，并在新的地方截断。创建一个tail 指针，作用有1:计算出链表长度，用于step数取模。2.将链表首位相连变成环。3:找到新的tail的位置方便截断。

代码

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

        tail = head        
        l = 0        
        while tail.next:
            l += 1
            tail = tail.next            
        l += 1

        tail.next = head

        k %= l
        step = l-k

        for _ in range(step):            
            head = head.next
            tail = tail.next

        tail.next = None

        return head

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

        l = 0

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

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

        slow = fast = head

        for _ in range(k):
            fast = fast.next

        while fast.next:
            slow = slow.next
            fast = fast.next

        new_head = slow.next

        slow.next = None
        fast.next = head

        return new_head
"""

复杂度

Time Complexity: O(n)

Space Complexity: O(1)

q815101630 commented 2 years ago

双指针

双指针，注意一些edge case

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

        cur = head
        fast = slow = head
        prev = None
        cnt = 0
        count = head
        while count:
            cnt += 1
            count = count.next  

        k = k%cnt

        if k == 0:
            return head

        while k>1:
            fast = fast.next
            k-=1
        while fast and fast.next:
            fast = fast.next
            prev = slow
            slow = slow.next
        fast.next = head
        if prev:
            prev.next = None
        return slow

时间 O(n) 空间 O(1)

zhangzz2015 commented 2 years ago

思路

比较直接，如果移动次数等于链表的元素个数，则回到原始链表。首先遍历链表，统计链表的个数N，然后对k%N求余数，移动次数范围为[0, N-1]。当为0时，则为原始链表，直接返回，考虑移动2次，对应把链表从N-2-1 处砍断，把最后前后位置交换。因此找到N- k -1 的链表元素，进行交换。时间仿真度为 O(N)，空间复杂度为O(1)。

关键点

代码

语言支持：C++

C++ 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 == NULL)
            return head; 
        ListNode* tail = NULL; 
        int listNum = CountNum(head, tail); 
        k = k%listNum; // [0 listNum); 
        if(k==0)
            return head; 
        k = listNum -k; // 1 --> 4   4 --->1. 

        ListNode* prevNode = moveKNode(head, k-1); 
        //  cut prevNode.  And put end into beginning. 
        ListNode* nextNode = prevNode->next; 
        prevNode->next = NULL;
        tail->next = head; 

        return nextNode;                         
    }

    int CountNum(ListNode* head, ListNode* & tail )
    {
        int i=0; 

        while(head)
        {
            tail = head; 
            head = head->next; 
            i++;
        }
        return i;             
    }

    ListNode* moveKNode(ListNode* head, int k)
    {
        // k>=1 K<= maxSize; 
        while(k)
        {
            head = head->next; 
            k--; 
        }
        return head; 
    }
};

rzhao010 commented 2 years ago

Thoughts

traverse the list to locate tail of the list
find the node to be the new head
connect the tail and head to make the list a ring
depart the ring at the new head

Code

    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || k == 0) {
            return head;
        }
        int n = 0;
        ListNode tail = null, tmp = head;
        // to get the length of list, and locate tail node
        while (tmp.next != null) {
            tail = tmp;
            n++;
            tmp = tmp.next;
        }
        k %= n; // in case k > n
        ListNode p = head;
        // locate (n - k)th node 
        for (int i = 0; i < n - k - 1; i++) {
            p = p.next;
        }
        // create a ring, then depart it at p.next, which is the new head
        tail.next = head;
        head = p.next;
        p.next = null;
        return head;
    }

Complexity

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

wangzehan123 commented 2 years ago

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(head == null){
            return null;
        }
        ListNode slow = head;
        int count = 1;
        while (slow.next != null){
            count ++;
            slow = slow.next;
        }
        // 尾结点
        ListNode tail = slow;
        k = k % count;
        if(k == 0){
            return head;
        }
        slow = head;
        ListNode fast = head;
        for(int i=0;i<k;i++){
            fast = fast.next;
        }
        while (fast.next != null){
            slow = slow.next;
            fast = fast.next;
        }
        ListNode newHead = slow.next;
        tail.next = head;
        slow.next = null;
        return newHead;
    }
}

yangziqi1998666 commented 2 years ago

/**
 * 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 || k == 0 || head.next == null)
            return head;
        int num = 0;
        ListNode tail = null;
        ListNode p = head;
        // find the length and tail of the list
        while(p != null){
            tail = p;
            p = p.next;
            num++;
        }
        // decide the back length when k is too large
        k %= num;
        // find the last node after rotation ( the k+1 th node from the tail)
        p = head;
        for(int i = 0; i < num - k - 1; i++)
            p = p.next;
        // do the cut and join operation
        tail.next = head;
        head = p.next;
        p.next = null;

        return head;
    }
}

ZhangNN2018 commented 2 years ago

思路

遍历链表，找出并记录原链表的尾节点m和长度n；
再次遍历链表，找到倒数第k+1个节点，该节点是旋转后的尾节点，next节点是新链表的头节点；
使该节点的next指向NULL；
使原先尾节点m的next指向原先的头节点head。

复杂度

时间复杂度: O(N), 2次遍历；
空间复杂度: O(1)。

代码

# 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):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        p=head #遍历链表，找出原链表的尾节点和长度
        q=head #遍历链表，找到倒数第k+1个节点，即新链表的头节点
        n=0 #n 记录链表的长度
        while p: 
            n=n+1
            m=p #记录原先的尾节点
            p=p.next

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

        kk=k%n #取余数
        if kk==0: # 等于0表示旋转后还是原来的样子
            return head

        j=1
        while q:
            if j==n-kk: #找出倒数第k+1个节点
                mm=q.next #这是旋转后的头节点
                q.next=p #该节点是旋转后的尾节点，该节点的next指向NULL
                m.next=head # 使原先尾节点的next指向原先的头节点
                break 
            q=q.next
            j=j+1

        return mm #返回旋转后的头节点

LannyX commented 2 years ago

思路

双指针，环形linked list

代码

/**
 * 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 || head.next == null) return head;

        int n = 1;
        ListNode iter = head;
        while(iter.next != null){
            iter = iter.next;
            n++;
        }
        k = k % n;

        ListNode slow = head;
        ListNode fast = head;

        while(fast.next != null){
            if(k <= 0){
                slow = slow.next;
            }
            fast = fast.next;
            k--;
        }        
        fast.next = head;
        ListNode res = slow.next;
        slow.next = null;

        return res;
    }
}

复杂度分析

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

Tao-Mao commented 2 years ago

Idea

Find the kth node, reverse it.

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 (head == null) return head;
        int i = 1;
        ListNode node = head;
        while (node.next != null) {
            ++i;
            node = node.next;
        }
        k = k % i;
        if (k == 0) return head;
        int j = i - k;

        ListNode tmp = head;
        while (j > 1 && tmp != null) {
            tmp = tmp.next;
            --j;
        }

        ListNode val = tmp.next;
        tmp.next = null;
        node.next = head;

        return val;
    }
}

Complexity

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

xj-yan commented 2 years ago

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

        length = self.getLength(head)
        if k % length == 0: return head
        k = length - k % length
        dummy = ListNode(0)
        curt = head

        while k > 1:
            curt = curt.next
            k -= 1
        newEnd = curt
        curt = curt.next
        newEnd.next = None
        dummy.next = curt
        while curt.next:
            curt = curt.next
        curt.next = head
        return dummy.next

    def getLength(self, head):
        count = 0
        curt = head
        while curt:
            count += 1
            curt = curt.next
        return count

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

falconruo commented 2 years ago

思路: 先计算单项链的长度n，并将链尾与链首相连，最后根据n和k的大小关系切断链表

复杂度分析:

时间复杂度: O(n), n为给定链表的长度
空间复杂度: O(1)

代码(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 || !head->next) return head;

        ListNode* p = head;
        int n = 1;
        while (p->next) {
            p = p->next;
            ++n;
        }

        int step = n - k % n;
        // p points to the last node
        p->next = head;

        while(step--) {
            head = head->next;
            p = p->next;
        }

        p->next = nullptr;
        return head;
    }
};

zhangzhengNeu commented 2 years 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; } }

CoreJa commented 2 years ago

思路

题目叫旋转链表，本质就是把链表头尾一连，然后转k下，再打开。

先遍历链表，头尾相连，顺便计数得到链表长度cnt

不用真的转k下，k先对cnt取余，再用cnt-取余的结果就是真正要转的次数，即k=cnt-k%cnt

再将p往后遍历k次，断开链表。

代码

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

herbertpan commented 2 years ago

思路

找到新的tail，做几个转换就可以找到新的head 了
但需要handle K 特别大的情况

code

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

        // get the list length
        int listLen = 1;
        ListNode pnt = head;
        while (pnt.next != null) {
            pnt = pnt.next;
            listLen++;
        }

        // to solve k > listLen problem
        k = k % listLen;

        // fast slow pointer to target new tail
        ListNode fast = head;
        ListNode slow = head;
        for (int i = 0; i < k; i++) {
            fast = fast.next;
        }

        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        // now fast is the tail and slow is new tail

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

        return newHead;
    }

复杂度分析

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

ZacheryCao commented 2 years ago

Idea:

Scan through the linkedlist to get its length (l) at first. Then redo the scan to get the node at l - (k%l). It's the new head. Disconnect the link between the new head and its previous node. Relink the old tail and the old head. Return the new head.

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 not head or not k:
            return head
        dummy = head
        length = 0
        tail = None
        while dummy:
            length += 1
            if not dummy.next:
                tail = dummy
            dummy = dummy.next
        if k%length==0:
            return head
        pre, newhead = None, head
        length -= k % length
        while length > 0:
            pre = newhead
            newhead = newhead.next
            length -= 1
        pre.next = None
        tail.next = head
        return newhead

Complexity:

Time: O(N) Space: O(1)

Bochengwan commented 2 years ago

思路

找点旋转后的head，然后断开和前一个node的链接。

代码

class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if not head or not k:
            return head

        curr = head
        l_len = 1
        while curr.next:
            curr = curr.next
            l_len+=1
        move = k%l_len

        curr.next = head

        curr = head

        for _ in range(l_len-move-1):
            curr = curr.next
        result = curr.next
        curr.next = None
        return result

复杂度分析

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

ZJP1483469269 commented 2 years 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]:
        node = head
        l = 0
        tail = head
        if not head:
            return head
        while node:
            l += 1
            if not node.next:
                tail = node
            node = node.next

        n = k % l 
        if n == 0:
            return head
        else:
            node = head
            for _ in range(l - n - 1):
                node = node.next
            new_head = node.next
            node.next = None
            tail.next = head
        return new_head

biaohuazhou commented 2 years ago

思路

找到链表长度和k 之间的关系，k决定了新的链表的表头，由此得到新的表头，然后将新表头的上一个链表的下一个链表置空原链表的最后一个数指向原链表的表头

代码

        class Solution {
        public ListNode rotateRight(ListNode head, int k) {
            if (head == null || head.next == null || k == 0) {
                return head;
            }
            int n = 1;
            ListNode node = head;
            while (node.next != null) {
                node = node.next;
                n++;
            }
            if(k%n==0)  return head;
            k = n - k % n;
            ListNode tmp = head;
            while (k > 1) {
                tmp = tmp.next;
                k--;
            }
            ListNode finhead = tmp.next;
            tmp.next = null;
            node.next = head;

            return finhead;

        }
    }

复杂度分析 时间复杂度： O(N) N为链表的长度空间复杂度：$O(1)$

feifan-bai commented 2 years ago

思路

slow, fast pointer
find the len of list
find the k node of list

find the new head node 代码

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

复杂度分析

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

Aobasyp commented 2 years ago

思路: 先计算单项链的长度n，并将链尾与链首相连，最后根据n和k的大小关系切断链表

class Solution { public: ListNode rotateRight(ListNode head, int k) { if (!head || !head->next) return head;

    ListNode* p = head;
    int n = 1;
    while (p->next) {
        p = p->next;
        ++n;
    }

    int step = n - k % n;
    // p points to the last node
    p->next = head;

    while(step--) {
        head = head->next;
        p = p->next;
    }

    p->next = nullptr;
    return head;
}

};

复杂度分析:

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

GaoMinghao commented 2 years ago

思路

把链表头尾相连，连城一个环，然后开始转

代码

class Solution {
    public static ListNode rotateRight(ListNode head, int k) {
        if(head == null) {
            return head;
        }
        ListNode pointer = head;
        int listSize = 1;
        while (pointer.next != null) {
            pointer = pointer.next;
            listSize ++;
        }
        pointer.next = head;
        int m = k / listSize;
        for(int i = 0; i < (m+1)*listSize-k;i++) {
            head = head.next;
            pointer = pointer.next;
        }
        pointer.next = null;
        return head;
    }
}

复杂度

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

wxj783428795 commented 2 years ago

思路

找到链表的tail，以及长度
将tail的next指向head，形成环。
在长度-k处断开链表即可

代码

/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var rotateRight = function (head, k) {
    if (!head) return head;
    let length = 1;
    let next = head;
    while (next.next) {
        length++;
        next = next.next;
    }
    //这时的next是链表的最后一个元素
    let move = k % length;
    if (!move) return head;
    //将tail的next指向head，形成环
    next.next = head;
    //然后再第length-move处断开环
    let step = length - move;
    let newTail = head;
    while (--step > 0) {
        newTail = newTail.next
    }
    let answer = newTail.next;
    newTail.next = null
    return answer
};

复杂度分析

复杂度分析不是很会，不一定对，如果有错，请指正。

时间复杂度：O(n) n为链表长度
空间复杂度：O(1)

Alexno1no2 commented 2 years ago

找尾节点，形成环形链表尾节点移动 length - k 步，（右移k步 == 左移 length - k 步）找到头节点，断开头尾连接

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

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

        k = k % length
        for _ in range(length - k):
            tail = tail.next

        head = tail.next
        tail.next = None
        return head

lilililisa1998 commented 2 years ago

循环链表的截断

class Solution(object): def rotateRight(self, head, k): if head==None or k==0: return head p=head while head.next!=None: head=head.next head.next=p #构建循环链表 i=0 while i<k:#选择断点 p=p.next q=p.next i=i+1 p.next=None return q 时间复杂度：O（n）

RocJeMaintiendrai commented 2 years ago

代码

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

复杂度分析

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

Davont commented 2 years ago

思路

感觉写的不是很好，两次遍历，第一次先算出长度（方便后期截断），同时为了尾部续接第一个。第二次是为了截断

code

var rotateRight = function(head, k) {
    let length = 1;
    let cur = head;
    if(cur === null) return null
    while(cur.next){
        length ++;
        cur = cur.next; 
    }
    cur.next = head; // 尾部续接
    let node = {
        val:head.val,
        next:null,
    }
    let cur2 = head;
    for(let i = 0;i<length-(k%length)-1;i++){
        cur2 = cur2.next;
    } 
    node.val = cur2.next.val;
    node.next = cur2.next;
    cur2.next = null;

    // head.val = node.val;
    // head.next = node.next;
    return node.next;
};

Myleswork commented 2 years ago

思路

找三个节点，头节点、尾节点、倒数第二个节点。每一次remote做如下操作：

1、尾节点指向头节点

2、倒数第二个节点更新为尾节点

3、尾节点更新为头节点

重复k次即可

但 k有可能很大，就要对链表长度取余，因为每循环链表长度次remote会和原链表相同。

代码

/**
 * 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 || head->next == nullptr) return head;
        int count = 1;
        ListNode* temp = head;
        while(temp->next != nullptr){
             count++;
             temp = temp->next;
        }
        k = k%count;
        while(k--){
            ListNode* cur = head;
            //找到倒数第二个节点
            while(cur->next->next != nullptr){
                cur = cur->next;
            }
            ListNode* tail = cur->next;   //尾节点
            tail->next = head;            //尾节点指向头节点
            cur->next = nullptr;          //倒数第二个节点成为尾节点
            head = tail;                  //更新头节点
        }
        return head;
    }
};

复杂度分析

时间复杂度：O(n) n为链表长度

空间复杂度：O(1)

Alyenor commented 2 years ago

思路设链表长度为 n，每旋转 n 次就会恢复原状，因此旋转 k 次取模即可，即计算 k % n 次。旋转 k 次，即把链表后 k 个节点移到开头，然后把结尾指向原来的头结点。

遍历链表，求长度，取 k % n
跳 n - k - 1 次，可以跳到后 k 个节点的前一个节点，将这个节点指向空节点，这个节点的下一个节点，作为头结点
尾节点指向原来的头结点
返回新的头结点

代码 function rotateRight(head: ListNode | null, k: number): ListNode | null { if (!head) return head; // 计算链表长度 let n = 0, p = head; while (p !== null) { n += 1; p = p.next!; } // 对 k 取模，如果等于零直接返回 k = k % n; if (!k) return head; // 找到 n-k-1 个节点 p = head; while (n - k - 1 > 0) { p = p.next!; n -= 1; } // 后一个节点是新的头结点 const newH = p!.next; // n-k-1 个节点指向 null p!.next = null; // 找到原来的尾节点，指向原来的头节点 let tail = newH; while (tail!.next != null) tail = tail!.next; tail!.next = head; // 返回新的头结点 return newH; }

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

yijing-wu commented 2 years ago

思路

代码


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

    ListNode old_tail = head;
    int n;
    for(n = 1; old_tail.next != null; n++)
      old_tail = old_tail.next;
    old_tail.next = head;

    // find new tail : (n - k % n - 1)th node
    // and new head : (n - k % n)th node
    ListNode new_tail = head;
    for (int i = 0; i < n - k % n - 1; i++)
      new_tail = new_tail.next;
    ListNode new_head = new_tail.next;

    new_tail.next = null;

    return new_head;
  }
}

复杂度分析

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

L-SUI commented 2 years ago

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 ret = cur.next;
cur.next = null;
return ret;

};

tongxw commented 2 years ago

思路

算出链表长度，找到实际的旋转次数 k % len
找倒数第k个节点的前面那个节点，顺便找到尾节点

头节点、尾节点、倒数第k个节点和它前面那个节点，这四个节点按照题意修改next指针。

代码

class Solution {
public ListNode rotateRight(ListNode head, int k) {
    int len = 0;
    ListNode p = head;
    while (p != null) {
        len++;
        p = p.next;
    }
    if (len == 0) {
        return head;
    }

    k = k % len;
    if (k == 0) {
        return head;
    }

    ListNode prev = head;
    ListNode tail = head;
    while (tail.next != null) {
        tail = tail.next;
        k--;
        if (k < 0) {
            prev = prev.next;
        }
    }

    ListNode newHead = prev.next;
    prev.next = null;
    tail.next = head;

    return newHead;
}
}

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

luoyuqinlaura commented 2 years ago

思路： loop through whole list, then 首尾相连，position = leng - k - 1处，断开连接，res = position.next; then position.next = NULL O(N), O(1)

代码： class solution{ public static ListNode reverseLink(ListNode head, int k) { ListNode res = NULL; ListNode cur = head; //corner case if (head == NULL || head.next = NULL) return head;

       int length = 1;
        while (cur.next != NULL) {
               cur = cur.next;
              length++;
           }

       //here connect head and tail
       cur.next = head;
      int pos = length - k - 1;

ListNode tail = head; for (int i = 0; i <= pos; i++) { tail = tail.next; }

res = tail.next; tail.next = NULL;

return res; }

z1ggy-o commented 2 years ago

思路

问题的核心是确认实际需要移动的量到底是多少。因为 k 的范围很大，我们可以利用取余的方式获得 list 长度内的实际有效移动量。

瞟了一眼 91 的题解和官方题解。其中提到的链表连环和快慢指针在本题当中都不是必要的。算法的复杂度核心还是在遍历过程本身。

代码

CPP

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        ListNode *tail;
        int len;

        if (!head)  // corner case
            return head;

        tail = head;
        len = 1;  // there is no dummy head
        while (tail->next) {
            tail = tail->next;
            len++;
        }

        int distance = k % len;
        if (distance == 0) {
            return head;
        }

        ListNode *tmp = head;
        // tmp points to the previous node of the new head
        for (int i = 0; i < len - distance - 1; i++) {
            tmp = tmp->next;
        }
        tail->next = head;
        head = tmp->next;
        tmp->next = nullptr;

        return head;
    }
};

复杂度分析

时间：O(N). N is the length of the linked list.
空间：O(1). In place, we only move the existed nodes.

wenlong201807 commented 2 years ago

代码块


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

  let count = 0;
  while (cur.next) {
      cur = cur.next;
      count++;
  }
  if (k === count) {
      return head;
  } else if (k > count) {
      k %= count;
  }

  cur.next = dummy.next;
  cur = cur.next;

  for (let i = 0; i < count - k - 1; i++) {
      cur = cur.next;
  }

  dummy.next = cur.next;
  cur.next = null;
  return dummy.next
};

时间复杂度和空间复杂度

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

watchpoints commented 2 years ago

思路

倒数第k个节点
链表特点不是swap ，是移动

代码

时间复杂度：O(n)

class Solution {
public:
   //小白视角分析
    // 4,5 ---怎么右移 从最后面变成最前面位置。 1,2,3  怎么右移
    // swap 还是移动 ？

    //时间复杂度：O(n)，最坏情况下，我们需要遍历该链表两次 
    //链表 不需要swap 

    //初级视角分析：
    //右移动 k 个位置 -->倒数第k个

    //中级视角分析：链表 环形队列的引用是
    ListNode* rotateRight(ListNode* head, int k) {

        if (NULL == head || NULL == head->next){
            return head;
        } 

        //构造一个环形链表 
        ListNode* ptemp = head;
        int size = 1;//最后一个不计算长度
        while (ptemp && ptemp->next )
        {
            ptemp = ptemp->next;
            size ++;
        } // ptemp ==last

        ptemp->next = head;//loop

        k = k % size;

        // 倒数第k个 前面一个位置。单链表特点  之前做法 双指针 

        while(  -- size >= k)
        {
             ptemp = ptemp->next;
        }

        ListNode* myhead = ptemp->next;
        ptemp->next = NULL;

        return myhead;
    }
};

Husky-Gong commented 2 years ago

Note

get new head
set tail.next = null
connect 2 parts
k = 0 and input is null

Code

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

        int size = 0;
        // get size
        ListNode sizeCurr = head;
        while (sizeCurr != null) {
            sizeCurr = sizeCurr.next;
            size++;
        }

        // get newhead
        ListNode temp = head;
        ListNode newTail = head;

        k = k % size;

        if (k == 0) {
            return head;
        }

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

        while (temp.next != null) {
            temp = temp.next;
            newTail = newTail.next;
        }

        ListNode newHead = newTail.next;
        newTail.next = null;

        //connect 2 parts
        temp.next = head;

        return newHead;
    }
}

Complexity

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

cszys888 commented 2 years ago

note

corner cases
count the length of linked list
connect the linked list and make it linked list loop
move forward until the new tail
cut it back into linked list (non-loop)

code

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

        cur = head
        n = 1

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

        cur.next = head

        move_next = n - k % n

        while move_next:
            cur = cur.next
            move_next -= 1

        new_head = cur.next
        cur.next = None

        return new_head

complexity

Time: O(N) Space: O(1)

baddate commented 2 years ago

题目

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

思路

首先遍历计算链表的大小sz；然后保存原始head指针为prev，为了之后链接头尾；对于k值，如果大于sz，其实会出现重复，所以我们直接计算k%sz，就是我们需要移动的次数；如果k%sz刚好是0，则不需要改变，直接返回head即可；我们通过计算temp=sz-k%sz可以计算出最终结果的头指针nhead，所以，再从头遍历链表，直到遍历到nhead前一个，即temp==1 的时候，我们需要将此时的指针next置空，否则最终结果就是环形链表了，但同时也要将nhead指向head->next作为最终返回值；最后，我们需要找到链表的尾指针，然后将尾指针指向我们之前保存的prev指针，返回nhead即可。

代码

/**
 * 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==NULL||head->next==NULL || k==0) return head;
        int sz=0;
        ListNode* ptr=head;
        while(ptr!=NULL)
        {
            ptr = ptr->next;
            sz++;
        }
        cout<<sz;
        k%=sz;
        ListNode* prev=head;
        int temp=sz-k;
        if(temp==sz) return head;
        while(head!=NULL&&temp!=1)
        {
            temp--;
            head=head->next;
        }
        ListNode* nhead=head->next;
        ListNode* tmp=head->next;

        head->next=nullptr;
        while(tmp!=NULL&&tmp->next!=NULL)
        {
            tmp=tmp->next;
        }
        tmp->next=prev;
        return nhead;
    }
};

复杂度分析

时间复杂度：O(N)，两次遍历链表
空间复杂度：O(1)，临时变量，常数空间

haixiaolu commented 2 years ago

思路：

将链表每个节点向右移动k个位置，相当于把链表的后面K % len 个节点移到链表的最前面

求链表的长度
找出倒数第 K + 1 个节点
将链表的倒数第K + 1个节点和倒数第K个节点断开，并把后半部分拼接到链表的头部

代码 / Python

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

        # length of the linked List
        length = 0
        cur = head
        while cur:
            length += 1
            cur = cur.next

        # mod of the length
        k %= length
        if k == 0:
            return head 

        # Two pointers
        fast, slow = head, head
        while k:
            fast = fast.next
            k -= 1

        # the distance between fast and slow is K: fast points K + 1 node
        # when fast.next is null, fast points to last node, slow points the K + 1 of last node
        while fast.next:
            fast = fast.next
            slow = slow.next

        # new head is the k of last node 
        new_head = slow.next
        slow.next = None
        fast.next = head
        return new_head

时空间复杂度分析

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

spacker-343 commented 2 years ago

思路

链表尾部接上头结点，第count-k节点的下一个节点为最新头结点，新的尾结点的next指针赋值为null

代码

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(head==null){
            return null;
        }
        int count=1;
        // 找到尾结点同时统计链表长度
        ListNode tail=head;
        while(tail.next!=null){
            count++;
            tail=tail.next;
        }
        // 防止循环走太多次，减少循环次数
        k %= count;
        if(k==0){
            // 取模后等于0说明不进行翻转
            // 向右移动数组长度个单位，就相当于没有移动
            return head;
        }
        // 将尾结点接上头结点
        tail.next=head;
        ListNode p=head;
        for(int i=1; i<count-k; i++){
            p=p.next;
        }
        // 从1开始，第count-k个节点的下一个节点为头结点
        head=p.next;
        // 第count-k个节点为新的尾结点
        p.next=null;
        return head;
    }
}

复杂度

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

pangjiadai commented 2 years ago

Python3

# 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]:
        # 旋转链表：k = k % length
        # 先遍历一遍得到length
        if not head or not head.next: return head

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

        # 将头尾连起来
        cur.next = head
        k = k % length 
        # 找到新的head
        for i in range(length-k):
            cur = cur.next

        newHead = cur.next
        cur.next = None

        return newHead

Yachen-Guo commented 2 years ago

思路：将linkedlist转化为list，在list中进行+step%mod操作，并且重建链表

时间复杂度：O(N)

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        int count = 0;
        ListNode node = head;
        if(head == null) return null;
        while(node != null){
            node = node.next;
            count++;
        }
        int[] list = new int[count];
        int idx = 0;
        ListNode ptr = head;
        for(int i = 0; i < count; i++){
            list[i] = ptr.val;
            ptr = ptr.next;
        }
        int[] tmp = new int[count];
        for(int j = 0; j < count; j++){
            int finalInd = (j+k) % count;
            tmp[finalInd] = list[j];
        }
        ListNode headNew = new ListNode(tmp[0]);
        ListNode iterNode = headNew;
        int iter = 1;
        while(iterNode != null && iter < count){
            iterNode.next = new ListNode(tmp[iter]);
            iter++;
            iterNode = iterNode.next;
        }
        return headNew;
    }
}

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

【Day 7 】2021-12-18 - 61. 旋转链表 #12

61. 旋转链表

入选理由

题目地址

前置知识

题目描述

Note

Solution (C++)

思路

代码（JAVA）

复杂度

思路

代码

复杂度

思路

代码

思路

代码

Problem

Note

Solution

Complexity

思路

代码

复杂度

双指针

思路

关键点

代码

思路

复杂度

代码

思路

代码

Idea

Code

Complexity

思路

代码

思路

code

复杂度分析

Idea:

Code

Complexity:

思路

代码

思路

代码

思路

代码

复杂度

思路

代码

复杂度分析

循环链表的截断

代码

思路

code

思路

代码

思路

代码

思路

代码

思路

代码

代码块

时间复杂度和空间复杂度

思路

代码

Note

Code

Complexity

note

code

complexity

题目

思路