Sắp xếp theo chẵn ở đầu, lẻ ở sau trong Linked List

chris_g · October 1, 2019, 3:22pm

Chào các bác, em đang sắp xếp 1 danh sách đã cho thành danh sách mới có phần tử chẵn nằm đầu danh sách và lẻ nằm ở cuối, nhưng mà em đã sắp xếp được chẵn ở đầu rồi, nhưng thứ tự phần lẻ phía sau lại sai. Các bác giúp em với.

void segregateEvenOdd(SinglyLinkedList* head_ref)
{
    // TODO
	SinglyLinkedListNode* p = head_ref->head;
	for (p; p != head_ref->tail; p = p->next) {
		for (SinglyLinkedListNode* k = p->next; k != NULL; k = k->next) {
			if (p->data % 2 != 0 && k->data % 2 == 0) {
				int temp;
				temp = p->data;
				p->data = k->data;
				k->data = temp;
			}
		}
	}
}

Vd: 8 >> 5 >> 4 >> 3 >> 1 >> 2 >> 6
Output: 8 >> 4 >> 2 >> 6 >> 5 >> 3 >> 1
Nhưng mà em lại ra là 8 >> 4 >> 2 >> 6 >> 1 >> 5 >> 3

rogp10 · October 1, 2019, 4:10am

Bài này bứt ra lựa lại rồi gắn lại là ổn nhất.

KuroShiro · October 1, 2019, 4:12am

mình nghĩ tạo một dslk mới rồi lặp qua từng phần tử của dslk cũ, nếu phân tử đấy là chẵn thì thêm vào đầu dslk mới còn nếu phần tử lẻ thì thêm vào cuối

tntxtnt · October 1, 2019, 4:23am

ko được tạo dslk mới, làm vậy vừa phải tạo node mới new/delete rất nhiều, rất chậm, vừa invalidate các con trỏ trỏ tới các node trong dslk này :V Ví dụ node chứa số 5 có địa chỉ là 0x555 thì sau khi sắp xếp node này cũng phải còn đúng địa chỉ 0x555 thì mới bảo toàn tính năng của dslk :V

edit: chắc đọc hiểu lầm, tạo dslk mới ok, đừng tạo new node là được

chris_g · October 1, 2019, 4:36am

Mình đã làm theo cách của bạn, mình tạo 1 list mới tên là newList, và cuối mình gán head_ref = newList;, nhưng kết quả thì vẫn như input

void segregateEvenOdd(SinglyLinkedList* head_ref)
{
	// TODO
	SinglyLinkedListNode* p = head_ref->head;
	SinglyLinkedList* newList = new SinglyLinkedList;
	for (p; p != head_ref->tail; p = p->next) {
		if (p->data % 2 == 0) {
			newList->insert_node(p->data);
		}
	}
	for (p; p != head_ref->tail; p = p->next) {
		if (p->data % 2 != 0) {
			newList->insert_node(p->data);
		}
	}
	head_ref = newList;

tntxtnt · October 1, 2019, 5:15am

tạo dslk mới bằng cách insert node mới vào là “sai” rồi, dù có in ra kết quả đúng thì vẫn bị invalidate con trỏ :V swap giá trị cũng làm invalidate con trỏ :V nếu có tạo dslk tạm thì phải đi gán node cũ vào chứ đừng tạo node mới

thử cách như thế này

if (!pHead) return; // empty list
Node *pe, *po;
for (pe = pHead; pe && pe->data % 2; pe = pe->next);
for (po = pHead; po && po->data % 2 == 0; po = po->next);
if (!po || !pe) return; // all odd or all even

/* 1 → 5 → 6 → 2 → 3 → ...
   ^po     ^pe */
if (pe != pHead)
{
    while (po->next != pe) po = po->next;
    /* 1 → 5 → 6 → 2 → 3 → ...
           ^po ^pe */
    
    po->next = pe->next;
    /* 1 → 5 → 2 → 3 → ...
           ^po ↑
               6 <pe */
           
    pe->next = pHead;
    /* 6 → 1 → 5 → 2 → 3 → ...
       ^pe ^po */

    pHead = pe;
}

/* 6 → 4 → 1 → 5 → 2 → 3 → ...
   ^pe     ^po */
while (1)
{
    while (pe->next->data % 2 == 0) pe = pe->next;
    /* 6 → 4 → 1 → 5 → 2 → 3 → ...
           ^pe ^po */
    
    while (po->next && po->next->data % 2) po = po->next;
    /* 6 → 4 → 1 → 5 → 2 → 3 → ...
           ^pe     ^po */
    
    /* 6 → 4 → 1 → 5 → NULL
           ^pe     ^po */
    if (!po->next) break;
    
    Node* poe = po->next;
    /* 6 → 4 → 1 → 5 → 2 → 3 → ...
           ^pe     ^po ^poe */
    
    po->next = poe->next;
    /* 6 → 4 → 1 → 5 → 3 → ...
           ^pe     ^po ↑
                       2 <poe */
    
    poe->next = pe->next;
    /* 6 → 4 → 1 → 5 → 3 → ...
           ^pe ↑   ^po 
               2 <poe */
    
    pe->next = poe;
    /* 6 → 4 → 2 → 1 → 5 → 3 → ...
           ^pe ^   ^po */
}

chạy thử :V https://rextester.com/LGXV7019

nitro2 · October 1, 2019, 3:23pm

Bạn này viết code comment có tâm ghê luôn

tntxtnt · October 1, 2019, 12:55pm

version vô tâm:

if (!pHead) return;
Node *pe, *po;
for (pe = pHead; pe && pe->data % 2; pe = pe->next) {}
for (po = pHead; po && po->data % 2 == 0; po = po->next) {}
if (!po || !pe) return;
if (pe != pHead) {
    while (po->next != pe) po = po->next;
    po->next = std::exchange(pe->next, std::exchange(pHead, pe));
}
while (1) {
    while (pe->next->data % 2 == 0) pe = pe->next;
    while (po->next && po->next->data % 2) po = po->next;
    if (!po->next) break;
    po->next =
        std::exchange(po->next->next, std::exchange(pe->next, po->next));
}