Решение Leetcode для поворота списка  


Сложный уровень средний
Часто спрашивают в саман Амазонка Bloomberg Facebook LinkedIn Microsoft Samsung
алгоритмы кодирование Интервью подготовка к собеседованию LeetCode LeetCodeSolutions Связанный список Два указателя

Задача «Повернуть список» Leetcode Solution предоставляет нам связанный список и целое число. Нам предлагается повернуть связанный список вправо на k мест. Итак, если мы поворачиваем связанный список на k позиций вправо, на каждом шаге мы берем последний элемент из списка и помещаем его из. Мы повторять это до тех пор, пока мы не сделаем k таких операций. Давайте посмотрим на несколько примеров.

head = [1,2,3,4,5], k = 2
[4,5,1,2,3]

Объяснение: Давайте разделим операцию на 2 простые операции поворота. Итак, на первом шаге или шаге мы просто берем элемент из конца списка и помещаем его впереди. Итак, список становится [5, 1, 2, 3, 4]. Теперь мы снова повторяем ту же операцию, составляя список, [4, 5, 1, 2, 3]. Отсюда и ответ.

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

Объяснение: Если повторить процесс 4 раза, появится связанный список ответов. Это можно лучше понять, посмотрев на изображение ниже.

Решение Leetcode для поворота спискашпилька

Подход к решению Leetcode с вращением списка  

Проблема «Повернуть список» Leetcode Solution гласит, что вам предоставляется связанный список с целым числом для вращения. Это означает, что нам нужно повернуть список на k позиций вправо. Проблему можно понять, просто взяв элементы из конца списка и разместив их впереди. Поскольку нет возможности эффективно снимите элемент с торца и поместите его впереди. Нам нужно подумать о любом другом способе выполнения операции. Если мы наблюдаем, мы можем видеть, что после выполнения k операций k элементов с конца удаляются и помещаются впереди. Здесь следует отметить одну вещь: если размер k больше, чем размер связанный список. Мы возьмем модуль k по длине связанный список.

Смотрите также
Найдите узел с минимальным значением в дереве двоичного поиска

После этого мы будем двигаться, пока k-й узел с конца. Затем выполняем некоторые операции, присваиваем головке следующий из последнего узла. Назначьте k-й узел с конца в качестве главы связанного списка. Но мы не должны забывать о присвоении следующего узла k-1-го узла с конца как null. Теперь, выполнив эти 3 операции, мы повернули список.

Код для решения Leetcode с вращением списка  

Код C ++

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

struct ListNode{
    int data;
    ListNode* next;
};

ListNode* rotateRight(ListNode* head, int k) {
    if(head==NULL || head->next==NULL)return head;

    ListNode *tmp = head;
    int cnt = 0;
    while(tmp)tmp=tmp->next,cnt++;
    tmp=head;
    k%=cnt;
    if(k==0)return head;

    while(k--)tmp = tmp->next;
    ListNode *tmpHead = head;
    while(tmp->next!=NULL){
        tmp = tmp->next;
        head = head->next;
    }
    ListNode* newHead = head->next;
    tmp->next = tmpHead;
    head->next = NULL;
    return newHead;
}

int main(){
    ListNode *head = new ListNode();
    head->data = 0;
    head->next = new ListNode();
    head->next->data = 1;
    head->next->next = new ListNode();
    head->next->next->data = 2;

    head = rotateRight(head, 4);
    while(head != NULL){
        cout<<head->data<<" ";
        head = head->next;
    }
}
2 0 1

Код Java

import java.util.*;
import java.lang.*;
import java.io.*;

class ListNode{
  int data;
  ListNode next;
}

class Solution {
    public static ListNode rotateRight(ListNode head, int k) {
        if(head==null || head.next==null)return head;
    
        ListNode tmp = head;
        int cnt = 0;
        while(tmp != null){
            tmp=tmp.next;
            cnt++;
        }
        tmp=head;
        k %= cnt;
        if(k==0)return head;

        while(k-- > 0)
            tmp = tmp.next;
        ListNode tmpHead = head;
        while(tmp.next != null){
            tmp = tmp.next;
            head = head.next;
        }
        ListNode newHead = head.next;
        tmp.next = tmpHead;
        head.next = null;
        return newHead;
    }
    
    public static void main(String[] args){
    	ListNode head = new ListNode();
      head.data = 0;
      head.next = new ListNode();
      head.next.data = 1;
      head.next.next = new ListNode();
      head.next.next.data = 2;
  
      head = rotateRight(head, 4);
      while(head != null){
          System.out.print(head.data + " ");
          head = head.next;
      }
    }
}
2 0 1

Анализ сложности  

Сложность времени

НА), где N представляет размер связанного списка. Поскольку мы должны перемещаться по связанному списку, временная сложность линейна и зависит от размера списка.

Смотрите также
Решение Leetcode изоморфных строк

Космическая сложность

О (1), поскольку нам не нужно хранить информацию для каждого из узлов. Таким образом, сложность пространства постоянна.

1