Bài 24 Leetcode: Swap Nodes in Pairs

Đề bài:

Cho một danh sách liên kết, hoán đổi mỗi cặp nút liên tiếp nhau và trả về đầu của danh sách liên kết đó. Bạn phải giải quyết bài toán mà không thay đổi các giá trị trong các nút của danh sách (nghĩa là chỉ có thể thay đổi các nút chính nó).

Ví dụ 1:

Swap Nodes in Pairs

Input: head = [1,2,3,4]
Output: [2,1,4,3]

Ví dụ 2:

Input: head = []
Output: []

Ví dụ 3:

Input: head = [1]
Output: [1]

Ràng buộc:

• Số lượng nút trong danh sách nằm trong khoảng [0, 100].
• 0 <= giá trị của nút <= 100.

Giải thích thuật toán bằng C++

class Solution {
 public:
  ListNode* swapPairs(ListNode* head) {
    const int length = getLength(head);
    ListNode dummy(0, head);
    ListNode* prev = &dummy;
    ListNode* curr = head;

    for (int i = 0; i < length / 2; ++i) {
      ListNode* next = curr->next;
      curr->next = next->next;
      next->next = prev->next;
      prev->next = next;
      prev = curr;
      curr = curr->next;
    }

    return dummy.next;
  }

 private:
  int getLength(ListNode* head) {
    int length = 0;
    for (ListNode* curr = head; curr; curr = curr->next)
      ++length;
    return length;
  }
};

Đây là một phương thức trong lớp `Solution`. Phương thức này được sử dụng để hoán đổi các cặp nút liên tiếp trong danh sách liên kết và trả về đầu của danh sách liên kết đã được hoán đổi.

Dưới đây là cách thuật toán hoạt động:

1. Phương thức `swapPairs` nhận đầu vào là một con trỏ `head` đến đầu của danh sách liên kết.

2. Sử dụng phương thức `getLength` để tính độ dài của danh sách liên kết.

3. Khởi tạo một nút giả `dummy` với giá trị 0 và con trỏ `next` trỏ tới `head`.

4. Khởi tạo hai con trỏ `prev` và `curr` trỏ tới `dummy` và `head` tương ứng.

5. Với mỗi vòng lặp từ 0 đến `length / 2`, thực hiện các bước sau:

a. Lấy con trỏ `next` trỏ tới nút kế tiếp của `curr`.

b. Gán con trỏ `next` vào nút tiếp theo của `curr`.

c. Gán con trỏ `prev` vào nút tiếp theo của `next`.

d. Gán con trỏ `next` vào nút tiếp theo của `prev`.

e. Di chuyển con trỏ `prev` và `curr` tới nút tiếp theo trong danh sách liên kết.

6. Trả về con trỏ đến nút đầu tiên của danh sách liên kết sau khi hoán đổi.

Thuật toán này sử dụng một phương pháp lặp để hoán đổi các cặp nút liên tiếp trong danh sách liên kết. Bắt đầu bằng việc khởi tạo một nút giả và hai con trỏ `prev` và `curr` trỏ tới nút đầu tiên của danh sách. Trong mỗi bước, ta lấy con trỏ `next` trỏ tới nút kế tiếp của `curr`, sau đó hoán đổi các liên kết giữa các nút để hoán đổi cặp nút hiện tại. Sau đó, di chuyển con trỏ `prev` và `curr` tới cặp nút tiếp theo và tiếp tục quá trình hoán đổi cho đến khi không còn cặp nút để hoán đổi. Cuối cùng, trả về đầu của danh sách liên kết đã được hoán đổi.

Giải thích thuật toán bằng Java

class Solution {
  public ListNode swapPairs(ListNode head) {
    final int length = getLength(head);
    ListNode dummy = new ListNode(0, head);
    ListNode prev = dummy;
    ListNode curr = head;

    for (int i = 0; i < length / 2; ++i) {
      ListNode next = curr.next;
      curr.next = next.next;
      next.next = curr;
      prev.next = next;
      prev = curr;
      curr = curr.next;
    }

    return dummy.next;
  }

  private int getLength(ListNode head) {
    int length = 0;
    for (ListNode curr = head; curr != null; curr = curr.next)
      ++length;
    return length;
  }
}

Giải thích thuật toán bằng Python

class Solution:
  def swapPairs(self, head: ListNode) -> ListNode:
    def getLength(head: ListNode) -> int:
      length = 0
      while head:
        length += 1
        head = head.next
      return length

    length = getLength(head)
    dummy = ListNode(0, head)
    prev = dummy
    curr = head

    for _ in range(length // 2):
      next = curr.next
      curr.next = next.next
      next.next = prev.next
      prev.next = next
      prev = curr
      curr = curr.next

    return dummy.next

 

The post Bài 24 Leetcode: Swap Nodes in Pairs first appeared on Techacademy.