18 bài toán về danh sách liên kết

Danh sách liên kết là một khái niệm rất cơ bản trong Lập trình. Việc tìm hiểu về danh sách liên kết trong C/C++ có nhiều điểm thú vị là vì:

• Cấu trúc của danh sách liên kết rất đơn giản, việc mô tả nó rất dễ dàng
• Tuy vậy các giải thuật xử lý danh sách liên kết lại có thể rất phức tạp và thú vị
• Làm việc với danh sách liên kết đòi hỏi việc sử dụng con trỏ một cách thành thạo
• Các danh sách liên kết đặc biệt phù hợp cho việc mô tả dùng hình vẽ. Làm việc với chúng giúp bạn phát triển kỹ năng hình tượng hóa vấn đề khi lập trình

Bài viết này sẽ điểm qua một số khái niệm cơ bản về danh sách liên kết và đưa ra 18 bài toán về danh sách liên kết theo thứ tự từ dễ đến khó.

Cơ bản về danh sách liên kết

Cấu trúc của một danh sách liên kết đơn như sau:

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

Chúng ta sẽ điểm qua một vài hàm cơ bản dùng để làm việc với danh sách. Hàm tính độ dài của danh sách như sau:

int Length(struct node *head) {
        int count =0;
        struct node *elem = head;
        while (elem) {
                count ++;
                elem = elem->next;
        }
        return count;
}

Hàm thêm một phần tử vào đầu danh sách:

void Push(struct node** headRef, int data) {
 struct node* newNode = malloc(sizeof(struct node));
 newNode->data = data;
 newNode->next = *headRef; // The '*' to dereferences back to the real head
 *headRef = newNode; // ditto
}

Chúng ta có thể dùng hàm sau để xây dựng một danh sách kết nối đơn giản, dùng làm đầu vào cho các bài toán ở phần sau:

struct node *BuildOneTwoThree() {
        struct node *head = NULL;
        struct node *second = NULL ;
        struct node *third = NULL;

        head = (struct node*) malloc(sizeof (struct node));
        second = (struct node*) malloc(sizeof (struct node));
        third = (struct node*) malloc(sizeof (struct node));

        if (!head || !second || !third) {
                printf("cannot allocate memory\n");
                exit(1);
        }
        head->data=1;
        head->next=second;

        second->data=2;
        second->next=third;

        third->data=3;
        third->next=NULL;

        return head;
}

18 bài toán về danh sách liên kết

1.  Count()

Viết hàm Count() thực hiện việc đếm các lần xuất hiện của một số nguyên trong một danh sách. 

void CountTest() {
 List myList = BuildOneTwoThree(); // build {1, 2, 3}
 int count = Count(myList, 2); // returns 1 since there's 1 '2' in the list
}

Mẫu hàm:

/* Given a list and an int, return the number of times that int occurs in the list. */
int Count(struct node* head, int searchFor) {
 // Your code
}

2. Nth()

Viết hàm Nth() trả về đối tượng thứ n trong danh sách (bắt đầu từ 0)

void GetNthTest() {
 struct node* myList = BuildOneTwoThree(); // build {1, 2, 3}
 int lastNode = GetNth(myList, 2); // returns the value 3 
}

Mẫu hàm:

// Given a list and an index, return the data
// in the nth node of the list. The nodes are numbered from 0.
// Assert fails if the index is invalid (outside 0..lengh-1).
int GetNth(struct node* head, int index) {
 // Your code
}

3. DeleteList()

Viết hàm DeleteList() để xóa một danh sách liên kết và thiết lập con trỏ head thành NULL

void DeleteListTest() {
 struct node* myList = BuildOneTwoThree(); // build {1, 2, 3}
 DeleteList(&myList); // deletes the three nodes and sets myList to NULL
}

Mẫu hàm:

void DeleteList(struct node** head) {
 // Your code
}

4. Pop()

Viết hàm Pop() để lấy ra phần tử đầu tiên của danh sách, phần từ này đồng thời được xóa khỏi danh sách.

void PopTest() {
 struct node* head = BuildOneTwoThree(); // build {1, 2, 3}
 int a = Pop(&head); // deletes "1" node and returns 1
 int b = Pop(&head); // deletes "2" node and returns 2
 int c = Pop(&head); // deletes "3" node and returns 3
 int len = Length(head); // the list is now empty, so len == 0
}

Mẫu hàm:

/*
The opposite of Push(). Takes a non-empty list
and removes the front node, and returns the data
which was in that node.
*/
int Pop(struct node** headRef) {
 // your code...
}

5. InsertNth()

Viết hàm để thêm vào danh sách một đối tượng tại vị trí thứ n

void InsertNthTest() {
 struct node* head = NULL; // start with the empty list
 InsertNth(&head, 0, 13); // build {13)
 InsertNth(&head, 1, 42); // build {13, 42}
 InsertNth(&head, 1, 5); // build {13, 5, 42}
 DeleteList(&head); // clean up after ourselves
}

Mẫu hàm:

/*
A more general version of Push().
Given a list, an index 'n' in the range 0..length,
and a data element, add a new node to the list so
that it has the given index.
*/
void InsertNth(struct node** headRef, int index, int data) {
 // your code...
}

6. SortedInsert()

Có một danh sách đã được sắp xếp. Viết hàm để thêm vào danh sách một đối tượng vào danh sách và giữ được thứ tự sắp xếp.

Mẫu hàm:

void SortedInsertNth(struct node** headRef,struct node *newNode) {
 // your code
}

7. InsertSort()

Nhận một danh sách đầu vào, sắp xếp danh sách này theo thứ tự tăng dần, bài toán yêu cầu sử dụng hàm SortedInsert() ở câu 6.

Mẫu hàm:

// Given a list, change it to be in sorted order (using SortedInsert()).
void InsertSort(struct node** headRef) { // Your code
}

8. Append()

Viết hàm nhận hai tham số là danh sách A và B, trả về danh sách A với B được gắn vào đuôi của A và B được thiết lập là NULL.

Mẫu hàm:

// Append 'b' onto the end of 'a', and then set 'b' to NULL.
void Append(struct node** aRef, struct node** bRef) {
 // Your code...
}

9. FronBackSplit()

Viết hàm tách một danh sách liên kết ra làm hai, ngắt ở giữa. Nếu chiều dài của danh sách là lẻ thì danh sách thứ nhất sẽ dài hơn danh sách thứ hai một phần tử.

Mẫu hàm:

/*
Split the nodes of the given list into front and back halves,
and return the two lists using the reference parameters.
If the length is odd, the extra node should go in the front list.
*/
void FrontBackSplit(struct node* source,
struct node** frontRef, struct node** backRef) {
 // Your code...
}

10. RemoveDuplicates()

Cho một danh sách đã được sắp xếp theo thứ tự tăng dần, hãy xóa các phần tử bị lặp với điều kiện danh sách chỉ được duyệt một lần.

Mẫu hàm:

/*
Remove duplicates from a sorted list.
*/
void RemoveDuplicates(struct node* head) {
 // Your code...
}

11. MoveNode()

Mẫu hàm:

/*
Take the node from the front of the source, and move it to
the front of the dest.
It is an error to call this with the source list empty.
*/
void MoveNode(struct node** destRef, struct node** sourceRef) {
 // Your code
}

12. ShuffleMerge()

Mẫu hàm:

/*
Merge the nodes of the two lists into a single list taking a node
alternately from each list, and return the new list.
*/
struct node* ShuffleMerge(struct node* a, struct node* b) {
 // Your code
}

Lời giải

1. Count()

int Count(struct node* head, int searchFor) {
 int count =0;
 struct node *element = head;
 while (element) {
  if ( element->data == searchFor) count++;
  element = element-> next;
 }
 return count;
}

2. Nth()

int GetNth(struct node* head, int index) {
        struct node *elem = head;
        int i = 0;

        while (elem) {
                if (i==index)
                        return elem->data;
                elem = elem->next;
                i++;
        }
        assert(0);
}

3. DeleteList()

void DeleteList(struct node **head) {
        struct node *elem = *head;
        struct node *another;
        while (elem) {
                another = elem->next;
                free(elem);
                elem = another;
        }
 *head = NULL;
}

4. Pop()

int Pop(struct node **head) {
        struct node *elem = *head;
        int a;
        assert( elem );
        a = elem->data;
        *head = elem->next;
        free(elem);
        return a;
}

5. InsertNth()

void InsertNth(struct node** head, int index, int data) {
        struct node *newElem;
        newElem = (struct node*) malloc(sizeof(struct node));
        newElem->data = data;
        int i = 0;
        struct node *elem = *head;
        while (elem) {
                if (i== (index-1)) {
                        newElem->next = elem->next;
                        elem->next = newElem;
                        break;
                }
                i++;
                elem = elem->next;
 }
}

6. SortedInsert()

void InsertNth(struct node** head, truct node *newNode) {
        struct node *elem = *head;
        while (elem) {
                if (newNode->data < elem->data) {
                        newNode->next = elem->next;
                        elem->next = newNode;
                        break;
                }
                elem = elem->next;
 }
}

7. InsertSort()

void InsertNth(struct node** head, truct node *newNode) {
}

8. Append()

void Append(struct node** aRef, struct node** bRef) {
 struct node *elem = *aRef;
 if (*aRef == NULL) {
  *aRef = *bRef;
 } else {
  while (elem->next) {
   elem = elem->next;
  }
  elem->next = *bRef;
 }
 *bRef = NULL;
}

9. FronBackSplit()

void FrontBackSplit(struct node* source, 
 struct node** frontRef, struct node** backRef) {
 if (source == NULL || source->next == NULL) {
  *frontRef = source;
  *backRef = NULL;
 } else {
  struct node *fast = source;
  struct node *slow = source->next;
  while (fast) {
   fast = fast->next;
   if (fast != NULL) {
    fast = fast->next;
    slow = slow->next;
   }
  }
  *frontRef = source;
  *backRef = slow->next;
  slow->next = NULL;
 }
}

....