โปรแกรมหมุน Linked List ไปขวา k ตำแหน่งใน C++

ภาพรวมปัญหา

ให้ Linked List และจำนวน k ต้องการหมุน linked list ไปทางขวา k ตำแหน่ง

ตัวอย่าง

Input: 1→2→3→4→5→NULL, k=2

แนวทางแก้ปัญหา

1. หาความยาว len และ tail node
2. เชื่อม tail→next = head (ทำให้เป็น circular)
3. k = k % len (ลด k ให้อยู่ในช่วง)
4. เดินจาก head ไป len-k-1 steps → newTail
5. newHead = newTail->next
6. newTail->next = NULL (ตัด circular)
7. คืนค่า newHead

โค้ดตัวอย่าง

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

class ListNode {
public:
    int val;
    ListNode *next;
    ListNode(int data) { val = data; next = NULL; }
};

ListNode* make_list(vector<int> v) {
    ListNode *head = new ListNode(v[0]);
    for (int i = 1; i < v.size(); i++) {
        ListNode *ptr = head;
        while (ptr->next) ptr = ptr->next;
        ptr->next = new ListNode(v[i]);
    }
    return head;
}

void print_list(ListNode *head) {
    ListNode *ptr = head;
    cout << "[";
    while (ptr) {
        cout << ptr->val;
        if (ptr->next) cout << ", ";
        ptr = ptr->next;
    }
    cout << "]" << endl;
}

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (!head) return head;
        
        int len = 1;
        ListNode* tail = head;
        while (tail->next) {
            len++;
            tail = tail->next;
        }
        
        tail->next = head; // Make circular
        k %= len;
        
        ListNode* newTail = head;
        for (int i = 0; i < len - k - 1; i++) {
            newTail = newTail->next;
        }
        
        ListNode* newHead = newTail->next;
        newTail->next = NULL;
        return newHead;
    }
};

int main() {
    Solution ob;
    vector<int> v = {1,2,3,4,5,6,7,8,9};
    ListNode *head = make_list(v);
    print_list(ob.rotateRight(head, 4));
    return 0;
}

ผลลัพธ์

[6, 7, 8, 9, 1, 2, 3, 4, ]

กรณีพิเศษ

• k = 0 หรือ k % len == 0 → คืนค่า head เดิม
• len = 1 → คืนค่า head เดิม
• head = NULL → คืนค่า NULL

ความซับซ้อน

• เวลา: O(N) — หาความยาว + หา newTail
• พื้นที่: O(1) — in-place, ไม่ใช้ memory เพิ่ม

ข้อควรระวัง

โค้ดต้นฉบับใน `make_list` ใช้ while loop หา tail ทุกครั้ง ทำให้ O(N²) ควรเก็บ tail ไว้ต่อท้ายโดยตรง

ListNode* make_list_fast(vector<int> v) {
    ListNode *head = new ListNode(v[0]);
    ListNode *tail = head;
    for (int i = 1; i < v.size(); i++) {
        tail->next = new ListNode(v[i]);
        tail = tail->next;
    }
    return head;
}