Xoay danh sách liên kết K bước

Nguồn: Hỏi đáp học viên Độ khó: Dễ Danh sách liên kết Con trỏ Cấu trúc dữ liệu

Đề bài

Xoay danh sách liên kết $K$ bước.

Ví dụ: danh sách liên kết là: 1 → 2 → 3 → 4 → 5

• $K = 2$: 4 → 5 → 1 → 2 → 3
• $K = 4$: 2 → 3 → 4 → 5 → 1

Dữ liệu vào và kết quả (mình bổ sung để các bạn chạy thử): đề gốc chỉ là một câu hỏi bài tập về danh sách liên kết nên không có định dạng nhập/xuất. Để tiện kiểm tra, trong bài này mình quy ước như sau:

• Dòng đầu gồm 2 số nguyên $n$ và $k$ $(1 \le n \le 10^5,\ 0 \le k \le 10^9)$: số phần tử của danh sách và số bước cần xoay.
• Dòng thứ hai gồm $n$ số nguyên (giá trị tuyệt đối không quá $10^9$) là các phần tử của danh sách theo thứ tự từ đầu đến cuối.
• Kết quả: in ra các phần tử của danh sách sau khi xoay $k$ bước, theo thứ tự từ đầu đến cuối, cách nhau một khoảng trắng.

Ví dụ 1 – input

5 2
1 2 3 4 5

Ví dụ 1 – output

4 5 1 2 3

Ví dụ 2 – input

5 4
1 2 3 4 5

Ví dụ 2 – output

2 3 4 5 1

Lời mở đầu

Bài này là câu hỏi của một em học viên nhắn cho mình: em ấy có ý tưởng là "ngắt liên kết cuối rồi đưa node cuối đó lên đầu, làm như vậy $k$ lần" mà loay hoay mãi chưa code ra được. Mình hướng dẫn qua tin nhắn khá kỹ, nên sẵn tiện viết lại thành bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Trước tiên mình hỏi lại em ấy: cấu trúc của danh sách liên kết là mình tự khai báo theo ý mình (miễn ra dạng danh sách liên kết), hay đề có bắt theo khuôn mẫu nào có sẵn không? Vì với câu này, nếu ta có thêm một con trỏ pTail đứng quản lý node cuối cùng của danh sách thì làm rất đơn giản 😃; còn nếu danh sách chỉ được quản lý bởi duy nhất con trỏ pHead thì làm sẽ phức tạp hơn một xíu. Trong bài này mình dùng cấu trúc quen thuộc có cả pHead lẫn pTail:

struct Node
{
    int Data;
    struct Node *pNext;
};
typedef struct Node NODE;

struct List
{
    NODE *pHead, *pTail;
};
typedef struct List LIST;

Hiểu rõ đề bài trước đã. Với danh sách 1 → 2 → 3 → 4 → 5:

• $k = 1$ (xoay 1 bước): 5 → 1 → 2 → 3 → 4
• $k = 2$ (xoay 2 bước): 4 → 5 → 1 → 2 → 3
• $k = 3$ (xoay 3 bước): 3 → 4 → 5 → 1 → 2
• $k = 4$ (xoay 4 bước): 2 → 3 → 4 → 5 → 1
• $k = 5$ (xoay 5 bước): 1 → 2 → 3 → 4 → 5 (trở về lại danh sách như ban đầu)

Và tương tự nếu $k = 6$ thì giống như $k = 1$, $k = 7$ thì giống như $k = 2$, cứ thế... Tức là xoay $n$ bước thì danh sách quay về y như cũ, nên chỉ cần xoay $k \bmod n$ bước là đủ.

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Đem node cuối lên đầu k lần · O(n·k)Cách 2Cắt và nối 1 lần tại node n − k · O(n)

Cách 1Đem node cuối lên đầu, làm k lần – O(n·k)

Nếu nhìn vào các ví dụ ở trên sẽ thấy rõ bản chất của nó: cứ với 1 lần xoay thì ta đem node ở cuối cùng danh sách đem lên trên đầu.

Quay lại với danh sách 1 → 2 → 3 → 4 → 5 và $k = 2$, tức là xoay 2 lần:

• Lần xoay đầu tiên: đem node cuối cùng của danh sách hiện tại (node 5) lên trên đầu; như thế node cuối cùng bây giờ chỉ là node 4, lúc này danh sách là 5 → 1 → 2 → 3 → 4.
• Vì $k = 2$ nên phải xoay thêm 1 lần nữa: đem node cuối cùng của danh sách hiện tại (node 4) lên đầu; node cuối cùng giờ là node 3, danh sách là 4 → 5 → 1 → 2 → 3.

Vậy ý tưởng ở đây là: ta viết một hàm tách node cuối cùng ra khỏi danh sách (RemoveTail), sau đó chèn node đó vào đầu danh sách (AddHead), và gọi cặp thao tác này $k$ lần là sẽ có được danh sách sau cùng 😃. Đây cũng chính là ý tưởng ban đầu của em học viên.

RemoveTail cần tìm node đứng trước node cuối

Danh sách liên kết đơn chỉ có con trỏ pNext đi tới, không đi lùi được. Nên muốn tách node cuối ra thì phải đi từ pHead tìm node p đứng ngay trước pTail, rồi cho p->pNext = NULL và pTail = p. Việc tìm này mất $O(n)$ cho mỗi lần xoay.

Source code để các bạn tham khảo nếu làm theo hướng này (mình có thêm k %= n ngay đầu hàm RotateK theo nhận xét "xoay $n$ bước thì như không xoay" ở trên):

#include <iostream>
using namespace std;

struct Node
{
    int Data;
    struct Node *pNext;
};
typedef struct Node NODE;

struct List
{
    NODE *pHead, *pTail;
};
typedef struct List LIST;

void Init(LIST &l)
{
    l.pHead = l.pTail = NULL;
}

NODE* GetNode(int x)
{
    NODE *p = new NODE;
    p->Data = x;
    p->pNext = NULL;
    return p;
}

void AddHead(LIST &l, NODE *p)
{
    if(l.pHead == NULL)
        l.pHead = l.pTail = p;
    else
    {
        p->pNext = l.pHead;
        l.pHead = p;
    }
}

void AddTail(LIST &l, NODE *p)
{
    if(l.pHead == NULL)
        l.pHead = l.pTail = p;
    else
    {
        l.pTail->pNext = p;
        l.pTail = p;
    }
}

// Tách node cuối ra khỏi danh sách và trả về node đó
NODE* RemoveTail(LIST &l)
{
    NODE *last = l.pTail;
    if(l.pHead == l.pTail)
    {
        l.pHead = l.pTail = NULL;
        return last;
    }
    NODE *p = l.pHead;
    while(p->pNext != l.pTail) // tìm node đứng trước node cuối
        p = p->pNext;
    p->pNext = NULL;
    l.pTail = p;
    return last;
}

void Print(LIST l)
{
    for(NODE *p = l.pHead; p != NULL; p = p->pNext)
        cout << p->Data << " ";
}

void RotateK(LIST &l, int n, long long k)
{
    k %= n;
    for(int i = 0; i < k; i++)
        AddHead(l, RemoveTail(l)); // đem node cuối lên đầu
}

int main()
{
    int n;
    long long k;
    cin >> n >> k;
    LIST l;
    Init(l);
    for(int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        AddTail(l, GetNode(x));
    }
    RotateK(l, n, k);
    Print(l);
    return 0;
}

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class List:
    def __init__(self):
        self.head = self.tail = None


def add_head(l, p):
    if l.head is None:
        l.head = l.tail = p
    else:
        p.next = l.head
        l.head = p


def add_tail(l, p):
    if l.head is None:
        l.head = l.tail = p
    else:
        l.tail.next = p
        l.tail = p


def remove_tail(l):
    """Tách node cuối ra khỏi danh sách và trả về node đó"""
    last = l.tail
    if l.head is l.tail:
        l.head = l.tail = None
        return last
    p = l.head
    while p.next is not l.tail:  # tìm node đứng trước node cuối
        p = p.next
    p.next = None
    l.tail = p
    return last


def rotate_k(l, n, k):
    k %= n
    for _ in range(k):
        add_head(l, remove_tail(l))  # đem node cuối lên đầu


def print_list(l):
    res = []
    p = l.head
    while p is not None:
        res.append(str(p.data))
        p = p.next
    print(' '.join(res))


data = input().split()
n, k = int(data[0]), int(data[1])
a = input().split()
l = List()
for i in range(n):
    add_tail(l, Node(int(a[i])))
rotate_k(l, n, k)
print_list(l)

Đánh giá độ phức tạp của cách làm này:

• Không gian: chỉ dùng chính các node của danh sách, không tốn thêm bộ nhớ: $O(1)$ (không tính danh sách).
• Thời gian: mỗi lần xoay tốn $O(n)$ để tìm node đứng trước node cuối, xoay $k \bmod n$ lần nên tổng là $O(n \cdot (k \bmod n))$, trường hợp xấu cỡ $O(n^2)$.

Không gian$O(1)$

Thời gian$O(n \cdot k)$

Cách này tính ra không tối ưu

Tưởng tượng xem: giả sử ta có danh sách 1000 số từ 1 đến 1000, cần xoay $k = 999$ thì ta thừa biết danh sách sau cùng sẽ là 2 → 3 → 4 → ... → 1000 → 1. Vậy chẳng lẽ cứ phải làm 999 lần thao tác đi tách node cuối cùng rồi chèn node đó vào đầu? Như thế thì rất dở 😃. Với $n = 10^5$ và $k \bmod n = 99999$, bản C++ của cách này chạy trên máy mình mất hơn 20 giây.

Cách 2Cắt và nối lại một lần tại node thứ n − k – O(n)

Ta sẽ nhìn ra một hướng tối ưu hơn như sau. Để rõ hơn ta quay lại ví dụ danh sách có 5 số 1 → 2 → 3 → 4 → 5, giả sử $k = 3$. Ta sẽ hiểu là 3 số cuối cùng của danh sách sẽ được đem lên đầu, và $5$ (số lượng phần tử danh sách đang chứa) $-\ k$ (là 3) $= 2$, nghĩa là 2 node đầu danh sách bây giờ sẽ ở cuối. Như thế ta sẽ có kết quả: 3 → 4 → 5 → 1 → 2.

Vậy nhìn vào danh sách ban đầu 1 → 2 → 3 → 4 → 5 và danh sách sau khi xoay 3 → 4 → 5 → 1 → 2, ta phải nhìn ra mấu chốt để xử lý nó: ngay từ đầu ta đã xác định danh sách có $n = 5$ node, và $k = 3$ ⇒ $n - k = 2$. Lúc này ta duyệt danh sách từ đầu, đếm đủ đến node thứ 2 thì dừng:

• Đầu tiên xét node 1: count = 1.
• Tiếp đến xét node 2: count = 2. Lúc này thấy count == n - k, vậy ta sẽ hiểu rằng node kế tiếp sẽ chính là Head trong tương lai (tức là node 3), và node 2 hiện tại trong tương lai sẽ đóng vai trò là node cuối cùng (tức là trỏ pNext = NULL).

Khi đang đứng ở node 2 (con trỏ p), ta làm đúng 4 thao tác:

1. Tạo một con trỏ temp nhảy đến node tiếp theo của 2 (là node 3) để giữ liên lạc với các node phần sau node 2: NODE *temp = p->pNext;
2. Cho node 2 trỏ pNext = NULL (ý là cho hiểu node 2 bây giờ trở thành node cuối cùng của danh sách): p->pNext = NULL;
3. Con trỏ pTail đứng cuối danh sách (đang là node 5) sẽ trỏ pNext về pHead (là node 1): l.pTail->pNext = l.pHead;
4. Cập nhật lại: pTail là node 2 (l.pTail = p;) và temp (đang là node 3) là Head (l.pHead = temp;).

Như vậy lúc này danh sách đã thành 3 → 4 → 5 → 1 → 2. Chỉ cần duyệt danh sách đúng một lần là xong, không cần xoay từng bước nữa!

Ý chính

Xoay $k$ bước (với $0 \lt k \lt n$) = cắt danh sách ngay sau node thứ $n - k$, rồi nối nửa đầu vào sau nửa cuối. Node thứ $n - k$ thành pTail mới, node thứ $n - k + 1$ thành pHead mới.

Cái này nếu chỉ diễn đạt bằng lời thì khó hình dung, các bạn nên lấy tờ giấy ra vẽ 5 ô vuông tượng trưng cho 1, 2, 3, 4, 5 liên tiếp nhau rồi dò lại từng bước ở trên. Hoặc dùng khung minh hoạ dưới đây: nhập danh sách, $k$, rồi bấm Tiếp để xem từng bước. Ở ô "Cách xoay" các bạn chọn thử "Cách 1" để so sánh xem cách 1 phải đi lại bao nhiêu bước nhé.

Danh sách k Cách xoay Cách 2: cắt nối 1 lầnCách 1: node cuối lên đầu k lần

Ví dụ nhanh:

Mình có thêm 2 dòng so với bản code tay ban đầu

Hàm RotateK mình code tay hướng dẫn em học viên ban đầu chỉ tính tới trường hợp $0 \lt k \lt n$. Để chạy đúng với mọi $k$ theo quy ước nhập ở trên, mình thêm k %= n; và if(k == 0) return; ở đầu hàm. Vì sao cần:

• Nếu $k \gt n$ thì $n - k \lt 0$, count không bao giờ bằng $n - k$ ⇒ danh sách không được xoay (sai, ví dụ $k = 7$ phải giống $k = 2$).
• Nếu $k = 0$ (hoặc $k$ chia hết cho $n$ sau khi lấy dư) thì $n - k = n$, vòng lặp dừng ở node cuối: temp = NULL, rồi pTail->pNext = pHead tạo thành vòng lặp và pHead = NULL ⇒ hỏng danh sách.

Source code để các bạn tham khảo nếu làm theo hướng này. Các hàm Init, GetNode, AddTail, Print là các hàm cơ bản của danh sách liên kết, hàm chính là RotateK:

#include <iostream>
using namespace std;

struct Node
{
    int Data;
    struct Node *pNext;
};
typedef struct Node NODE;

struct List
{
    NODE *pHead, *pTail;
};
typedef struct List LIST;

void Init(LIST &l)
{
    l.pHead = l.pTail = NULL;
}

NODE* GetNode(int x)
{
    NODE *p = new NODE;
    p->Data = x;
    p->pNext = NULL;
    return p;
}

void AddTail(LIST &l, NODE *p)
{
    if(l.pHead == NULL)
        l.pHead = l.pTail = p;
    else
    {
        l.pTail->pNext = p;
        l.pTail = p;
    }
}

void Print(LIST l)
{
    for(NODE *p = l.pHead; p != NULL; p = p->pNext)
        cout << p->Data << " ";
}

// n là số phần tử trong danh sách, k là số bước xoay
void RotateK(LIST &l, int n, long long k)
{
    k %= n;
    if(k == 0) return;
    int count = 0;
    for(NODE *p = l.pHead; p != NULL; p = p->pNext)
    {
        count++;
        if(count == n - k)
        {
            NODE *temp = p->pNext;
            p->pNext = NULL;
            l.pTail->pNext = l.pHead;
            l.pTail = p;
            l.pHead = temp;
            break;
        }
    }
}

int main()
{
    int n;
    long long k;
    cin >> n >> k;
    LIST l;
    Init(l);
    for(int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        AddTail(l, GetNode(x));
    }
    RotateK(l, n, k);
    Print(l);
    return 0;
}

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class List:
    def __init__(self):
        self.head = self.tail = None


def add_tail(l, p):
    if l.head is None:
        l.head = l.tail = p
    else:
        l.tail.next = p
        l.tail = p


def rotate_k(l, n, k):
    k %= n
    if k == 0:
        return
    count = 0
    p = l.head
    while p is not None:
        count += 1
        if count == n - k:
            temp = p.next          # node sẽ làm Head mới
            p.next = None          # p trở thành node cuối
            l.tail.next = l.head   # nối đuôi cũ vào đầu cũ
            l.tail = p
            l.head = temp
            break
        p = p.next


def print_list(l):
    res = []
    p = l.head
    while p is not None:
        res.append(str(p.data))
        p = p.next
    print(' '.join(res))


data = input().split()
n, k = int(data[0]), int(data[1])
a = input().split()
l = List()
for i in range(n):
    add_tail(l, Node(int(a[i])))
rotate_k(l, n, k)
print_list(l)

Khung chạy tay dưới đây chạy đúng từng dòng của code C++ ở trên. Phần đầu là tạo danh sách bằng AddTail, các bạn có thể bấm Tiếp nhanh qua phần đó để tới đoạn RotateK (dòng 48 – 66):

C++▶ Chạy tay từng dòng codeĐếm tới node thứ n − k, rồi cắt sau node đó và nối pTail vào pHead cũ.

Dữ liệu vào (stdin) – sửa thoải mái5 2 1 2 3 4 5

Dữ liệu mẫu:

1#include <iostream>

2using namespace std;

3

4struct Node

5{

6 int Data;

7 struct Node *pNext;

8};

9typedef struct Node NODE;

10

11struct List

12{

13 NODE *pHead, *pTail;

14};

15typedef struct List LIST;

16

17void Init(LIST &l)

18{

19 l.pHead = l.pTail = NULL;

20}

21

22NODE* GetNode(int x)

23{

24 NODE *p = new NODE;

25 p->Data = x;

26 p->pNext = NULL;

27 return p;

28}

29

30void AddTail(LIST &l, NODE *p)

31{

32 if(l.pHead == NULL)

33 l.pHead = l.pTail = p;

34 else

35 {

36 l.pTail->pNext = p;

37 l.pTail = p;

38 }

39}

40

41void Print(LIST l)

42{

43 for(NODE *p = l.pHead; p != NULL; p = p->pNext)

44 cout << p->Data << " ";

45}

46

47// n là số phần tử trong danh sách, k là số bước xoay

48void RotateK(LIST &l, int n, long long k)

49{

50 k %= n;

51 if(k == 0) return;

52 int count = 0;

53 for(NODE *p = l.pHead; p != NULL; p = p->pNext)

54 {

55 count++;

56 if(count == n - k)

57 {

58 NODE *temp = p->pNext;

59 p->pNext = NULL;

60 l.pTail->pNext = l.pHead;

61 l.pTail = p;

62 l.pHead = temp;

63 break;

64 }

65 }

66}

67

68int main()

69{

70 int n;

71 long long k;

72 cin >> n >> k;

73 LIST l;

74 Init(l);

75 for(int i = 0; i < n; i++)

76 {

77 int x;

78 cin >> x;

79 AddTail(l, GetNode(x));

80 }

81 RotateK(l, n, k);

82 Print(l);

83 return 0;

84}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: chỉ dùng thêm vài biến con trỏ: $O(1)$ (không tính danh sách).
• Thời gian: duyệt danh sách tối đa một lần để tìm node thứ $n - k$, sau đó chỉ đổi 4 con trỏ: $O(n)$.

Không gian$O(1)$

Thời gian$O(n)$

Nếu danh sách chỉ có pHead, không có pTail?

Khi đó ta không biết trước $n$ và cũng không có sẵn node cuối. Ta chỉ cần duyệt thêm một lượt từ pHead để vừa đếm $n$ vừa tìm ra node cuối, rồi làm y như cách 2 ở trên. Tổng thời gian vẫn là $O(n)$, chỉ là code dài hơn một xíu thôi.

Quan trọng không phải là chỉ xem code, mà là hiểu rõ từng bước danh sách thay đổi ra sao. Các bạn hãy lấy một ví dụ cụ thể ra giấy, lần theo từng dòng code ở trên (hoặc bấm khung chạy tay) để hiểu rõ ràng nha. Còn lại thì phải luyện nhiều thôi 😃.

Ghi chú của mình: code C++ và Python của cả 2 cách đã được kiểm tra với 500 bộ test ngẫu nhiên ($n \le 12$, $k$ tới $10^9$, có cả $k = 0$, $k = n$, $k \gt n$), so với kết quả xoay mảng trực tiếp – khớp hết. Với $n = 10^5$ và $k \bmod n = 99999$: cách 2 bản C++ chạy khoảng 0.1 giây, bản Python khoảng 0.4 giây; còn cách 1 bản C++ mất hơn 20 giây đúng như phân tích.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇