Coi chúng ta có một danh sách được liên kết. Chúng ta phải hoán đổi mỗi hai nút liền kề và trả về phần đầu của nó. Ràng buộc là chúng ta không thể sửa đổi giá trị của các nút, chỉ có thể thay đổi chính nút đó. Vì vậy, nếu danh sách giống như [1,2,3,4], thì danh sách kết quả sẽ là [2,1,4,3]
Để giải quyết vấn đề này, chúng ta sẽ làm theo các bước sau -
- nếu phần đầu không xuất hiện, thì hãy quay lại phần đầu
- first:=head, second:=next of head, dummy là một nút mới có giá trị -1
- tiếp theo của dummy:=đầu tiên và trước:=dummy
- while thứ hai không rỗng
- temp:=next of second
- next of first:=next of second
- tiếp theo của giây:=đầu tiên
- tiếp theo của trước:=thứ hai
- trước:=đầu tiên
- nếu tạm thời không null, thì đầu tiên:=tạm thời và thứ hai:=tiếp theo của nhiệt độ, nếu không thì ngắt
- trở lại tiếp theo của hình nộm
Ví dụ (C ++)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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 != NULL){
ptr = ptr->next;
}
ptr->next = new ListNode(v[i]);
}
return head;
}
void print_list(ListNode *head){
ListNode *ptr = head;
cout << "[";
while(ptr->next){
cout << ptr->val << ", ";
ptr = ptr->next;
}
cout << "]" << endl;
}
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if(!head)return head;
ListNode* first= head;
ListNode* second = head->next;
ListNode* dummy = new ListNode(-1);
dummy->next = first;
ListNode* prev = dummy;
while(second){
ListNode* temp = second->next;
first->next = second->next;
second->next = first;
prev->next = second;
prev = first;
if(temp){
first = temp;
second = temp ->next;
}
else break;
}
return dummy->next;
}
};
main(){
Solution ob;
vector<int> v = {1,2,3,4,5,6,7,8};
ListNode *head = make_list(v);
print_list(ob.swapPairs(head));
} Đầu vào
[1,2,3,4,5,6,7,8]
Đầu ra
[2,1,4,3,6,5,8,7]