輪換名單Leetcode解決方案  


難度級別 中烘焙
經常問 土磚 亞馬遜 彭博社 Facebook LinkedIn Microsoft微軟 Samsung
算法 編碼 訪問 面試準備 力碼 力碼解決方案 鍊錶 兩個指針

問題 Rotate List Leetcode Solution 為我們提供了一個鍊錶和一個整數。 我們被告知將鍊錶向右旋轉 k 個位置。 因此,如果我們將鍊錶向右旋轉 k 位,則在每一步中,我們都會從鍊錶中取出最後一個元素並將其放入 from。 我們 重複 直到我們完成了 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解決方案的方法  

問題 Rotate List Leetcode Solution 指出您將獲得一個帶有整數的鍊錶用於旋轉。 這意味著我們需要將列表向右旋轉 k 個位置。 這個問題可以通過從列表末尾取出元素並將它們放在前面的簡單操作來理解。 由於沒有辦法 有效地 從末尾刪除一個元素並將其放在前面。 我們需要考慮任何其他方式來執行操作。 如果我們觀察,我們可以看到,在執行 k 個操作後,從末尾開始刪除 k 個元素並放在前面。 這裡要注意的一件事是,如果 k 的大小大於 鍊錶. 我們將在整個長度上取 k 的模 鍊錶.

也可以看看
在二叉搜索樹中找到最小值的節點

完成後,我們將遍歷直到 從末端算起的第 k 個節點. 然後我們執行一些操作,我們將最後一個節點的下一個分配給頭部。 指定從末尾開始的第 k 個節點作為鍊錶的頭。 但是我們不應該忘記將第 k-1 個節點的下一個節點從末尾分配為空。 現在,在執行了這 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解決方案

空間複雜度

O(1), 因為我們不需要為每個節點存儲信息。 因此,空間複雜度是恆定的。

1