92. Reverse Linked List II

LeetCode medium оригинал: C# #csharp #leetcode #linked-list #medium #recursion #two-pointers
LeetCode Static

Дан указатель на начало односвязного списка и два целых числа left и right, где left <= right. Необходимо перевернуть узлы списка, начиная с позиции left и заканчивая позицией right, и вернуть измененный список.

Пример:

Input: head = [1,2,3,4,5], left = 2, right = 4

Output: [1,4,3,2,5]

C# решение

сопоставлено/оригинал 
public class Solution {
    private ListNode left = null;
    private bool stop = false;
    public void recurseAndReverse(ListNode right, int m, int n) {
        if (n == 1)
            return;
        right = right.next;
        if (m > 1)
            this.left = this.left.next;
        this.recurseAndReverse(right, m - 1, n - 1);
        if (this.left == right || right.next == this.left)
            this.stop = true;
        if (!this.stop) {
            int tmp = this.left.val;
            this.left.val = right.val;
            right.val = tmp;
            this.left = this.left.next;
        }
    }
    public ListNode ReverseBetween(ListNode head, int m, int n) {
        stop = false;
        left = head;
        recurseAndReverse(head, m, n);
        return head;
    }
}

C++ решение

auto-draft, проверить перед отправкой 
#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:
    private ListNode left = null;
    private bool stop = false;
    public void recurseAndReverse(ListNode right, int m, int n) {
        if (n == 1)
            return;
        right = right.next;
        if (m > 1)
            this.left = this.left.next;
        this.recurseAndReverse(right, m - 1, n - 1);
        if (this.left == right || right.next == this.left)
            this.stop = true;
        if (!this.stop) {
            int tmp = this.left.val;
            this.left.val = right.val;
            right.val = tmp;
            this.left = this.left.next;
        }
    }
    public ListNode ReverseBetween(ListNode head, int m, int n) {
        stop = false;
        left = head;
        recurseAndReverse(head, m, n);
        return head;
    }
}

Java решение

сопоставлено/оригинал 
class Solution {
    private boolean stop;
    private ListNode left;

    public void recurseAndReverse(ListNode right, int m, int n) {
        if (n == 1) {
            return;
        }

        right = right.next;

        if (m > 1) {
            this.left = this.left.next;
        }

        this.recurseAndReverse(right, m - 1, n - 1);

        if (this.left == right || right.next == this.left) {
            this.stop = true;
        }

        if (!this.stop) {
            int t = this.left.val;
            this.left.val = right.val;
            right.val = t;

            this.left = this.left.next;
        }
    }

    public ListNode reverseBetween(ListNode head, int m, int n) {
        this.left = head;
        this.stop = false;
        this.recurseAndReverse(head, m, n);
        return head;
    }
}

JavaScript решение

сопоставлено/оригинал 
var reverseBetween = function (head, m, n) {
    let left = head,
        stop = false;
    const recurseAndReverse = (right, m, n) => {
        if (n == 1) return;
        right = right.next;
        if (m > 1) left = left.next;
        recurseAndReverse(right, m - 1, n - 1);
        if (left == right || right.next == left) stop = true;
        if (!stop) {
            [left.val, right.val] = [right.val, left.val];
            left = left.next;
        }
    };
    recurseAndReverse(head, m, n);
    return head;
};

Python решение

сопоставлено/оригинал 
class Solution:
    def reverseBetween(
        self, head: Optional[ListNode], m: int, n: int
    ) -> Optional[ListNode]:
        if not head:
            return None

        left, right = head, head
        stop = False

        def recurseAndReverse(right, m, n):
            nonlocal left, stop
            if n == 1:
                return
            right = right.next
            if m > 1:
                left = left.next
            recurseAndReverse(right, m - 1, n - 1)
            if left == right or right.next == left:
                stop = True
            if not stop:
                left.val, right.val = right.val, left.val
                left = left.next

        recurseAndReverse(right, m, n)
        return head

Go решение

сопоставлено/оригинал 
type Solution struct {
    stop bool
    left *ListNode
}

func (s *Solution) recurseAndReverse(right *ListNode, m int, n int) {
    if n == 1 {
        return
    }
    right = right.Next
    if m > 1 {
        s.left = s.left.Next
    }
    s.recurseAndReverse(right, m-1, n-1)
    if s.left == right || right.Next == s.left {
        s.stop = true
    }
    if !s.stop {
        t := s.left.Val
        s.left.Val = right.Val
        right.Val = t
        s.left = s.left.Next
    }
}

func reverseBetween(head *ListNode, m int, n int) *ListNode {
    sol := &Solution{left: head, stop: false}
    sol.recurseAndReverse(head, m, n)
    return head
}

Algorithm

1️⃣

Определяем рекурсивную функцию, которая будет отвечать за переворачивание части односвязного списка. Назовем эту функцию

recurse

. Функция принимает три параметра:

m

, начальную точку переворота,

n

, конечную точку переворота, и указатель

right

, который начинается с узла

n

в связанном списке и движется назад вместе с откатом рекурсии. Если это пока не ясно, следующие диаграммы помогут.

2️⃣

Также у нас есть указатель

left

, который начинается с узла

m

в связанном списке и движется вперед. В Python мы должны использовать глобальную переменную для этого, которая изменяется с каждым вызовом рекурсии. В других языках, где изменения, сделанные в вызовах функций, сохраняются, мы можем рассматривать этот указатель как дополнительную переменную для функции

recurse

.

В рекурсивном вызове, учитывая

m

,

n

и

right

, мы проверяем, равно ли

n

единице. Если это так, дальше двигаться не нужно.

3️⃣

До тех пор, пока мы не достигнем

n = 1

, мы продолжаем двигать указатель

right

на один шаг вперед, после чего делаем рекурсивный вызов с уменьшенным на один значением

n

. В то же время мы продолжаем двигать указатель

left

вперед до тех пор, пока

m

не станет равным 1. Когда мы говорим, что указатель движется вперед, мы имеем в виду

pointer.next

.

Таким образом, мы откатываемся, как только

n

достигает 1. В этот момент указатель

right

находится на последнем узле подсписка, который мы хотим перевернуть, и

left

уже достиг первого узла этого подсписка. Тогда мы меняем данные и перемещаем указатель

left

на один шаг вперед с помощью

left = left.next

. Нам нужно, чтобы это изменение сохранялось в процессе отката.

Оттуда при каждом откате указатель

right

движется на один шаг назад. Это и есть та симуляция, о которой мы всё время говорили. Обратное движение симулируется откатом.

Мы прекращаем обмены, когда

right == left

, что происходит, если размер подсписка нечетный, или

right.next == left

, что происходит в процессе отката для четного подсписка, когда указатель

right

пересекает

left

. Мы используем глобальный булевый флаг для остановки обменов, как только эти условия выполнены.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии
Активных вакансий пока нет.