61. Rotate List

leetcode medium

#csharp#leetcode#linked-list#medium#two-pointers

Task

Дан указатель на начало связного списка, поверните список вправо на k позиций.

Пример:

Input: head = [0,1,2], k = 4

Output: [2,0,1]

C# solution

matched/original

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

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    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;
        
        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;
    }
}

Java solution

matched/original

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;

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

JavaScript solution

matched/original

var rotateRight = function (head, k) {
    if (head == null) return null;
    if (head.next == null) return head;

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

    let new_tail = head;
    for (let i = 0; i < n - (k % n) - 1; i++) new_tail = new_tail.next;
    let new_head = new_tail.next;

    new_tail.next = null;
    return new_head;
};

Python solution

matched/original

class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[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

Go solution

matched/original

func rotateRight(head *ListNode, k int) *ListNode {
    if head == nil {
        return nil
    }
    if head.Next == nil {
        return head
    }
    old_tail := head
    n := 1
    for old_tail.Next != nil {
        n++
        old_tail = old_tail.Next
    }
    old_tail.Next = head
    new_tail := head
    for i := 1; i < n-k%n; i++ {
        new_tail = new_tail.Next
    }
    new_head := new_tail.Next
    new_tail.Next = nil
    return new_head
}

Explanation

Algorithm

1️⃣

Найдите старый хвост и соедините его с головой (old_tail.next = head), чтобы замкнуть кольцо. Одновременно вычислите длину списка n.

2️⃣

Найдите новый хвост, который находится на позиции (n - k % n - 1) от головы, и новую голову, которая находится на позиции (n - k % n).

3️⃣

Разорвите кольцо (new_tail.next = None) и верните new_head.

😎