Làm sao để copy địa chỉ của head trong linked list qua node khác

#1

Như tiêu đề ạ, nhưng khi em đưa nguyên hàm Rotation vào phía dưới hàm insert_node trong class SinglyLinkedList thì nó lại ra được kết quả đúng. Mọi người chỉ em với.
Code trong function Rotation là đưa node cuối lên node đầu tương ứng với số lần k
VD: list: 3-5-6-7, k=1 => 7-3-5-6
k=2 => 6->7-3-5

#include "pch.h"
#include <iostream>
#include <string>
#include <stack>
using namespace std; 
class SinglyLinkedListNode {
public:
	int data;
	SinglyLinkedListNode *next;

	SinglyLinkedListNode(int node_data) {
		this->data = node_data;
		this->next = nullptr;
	}
};

class SinglyLinkedList {
public:
	SinglyLinkedListNode *head;
	SinglyLinkedListNode *tail;

	SinglyLinkedList() {
		this->head = nullptr;
		this->tail = nullptr;
	}

	void insert_node(int node_data) {
		SinglyLinkedListNode* node = new SinglyLinkedListNode(node_data);

		if (!this->head) {
			this->head = node;
		}
		else {
			this->tail->next = node;
		}

		this->tail = node;
	}
	
};

void print_singly_linked_list(SinglyLinkedListNode* node, string sep) {
	while (node) {
		cout << node->data;
		node = node->next;
		if (node) {
			cout << sep;
		}
	}
}
void swap(SinglyLinkedListNode *a, SinglyLinkedListNode *b)
{
	int temp = a->data;
	a->data = b->data;
	b->data = temp;

}



void Rotation(SinglyLinkedListNode * head, int k)
{
	while (k > 0)
	{
		SinglyLinkedListNode *preLast = head, *first = head;
		while (preLast->next->next)
		{
			preLast = preLast->next;
		}
		SinglyLinkedListNode *last = preLast->next;
			preLast->next = NULL;
			last->next = first;
			head = last;
			k--;
	}
	
}


int main()
{
	SinglyLinkedList *llist = new SinglyLinkedList();
	llist->insert_node(3);
	llist->insert_node(5);
	llist->insert_node(6);
	llist->insert_node(7);
	Rotation(llist->head,1);
	print_singly_linked_list(llist->head, " ");
	return 0;
}
#3 
void Rotation(SinglyLinkedListNode * head, int k)
{
	while (k > 0)
	{
		SinglyLinkedListNode *preLast = head, *first = head;
		while (preLast->next->next)
		{
			preLast = preLast->next;
		}
		SinglyLinkedListNode *last = preLast->next;
			preLast->next = NULL;
			last->next = first;
			head = last;
			k--;
	}
	
}

// code như này là thấy k ổn rồi, phải tính trường hợp head=null, head chỉ chứa 1 node , như vậy hàm Rotation của bạn sẽ bị error ngay

mình gợi ý cho bạn là

  1. Cho k tăng dần

  2. lastNode->next = firstNode

  3. penultimateNode->next=null

2 Likes
#4

Mình có thể thêm

if(head == NULL || head->next ==NULL) return;

Nhưng đó vẫn không phải là vấn đề mà mình gặp phải. Mình gặp nhiều bài cần phải sao chép địa chỉ của head thì mình không thể làm được.

#5 
void Rotation(SinglyLinkedListNode * head, int k)
{	
	SinglyLinkedListNode * headTemp = head;
	for (int i=1;i<=k;i++) {
		SinglyLinkedListNode *firstNode,*penultimateNode = headTemp;
		while(penultimateNode->next->next!=null) {
			penultimateNode=penultimateNode->next;
		}
		SinglyLinkedListNode *lastNode = penultimateNode->next;
		lastNode->next=firstNode;
		penultimateNode->next=null;
		headTemp= lastNode;
	}
	return headTemp;
}
#7

Mình nghĩ code của bạn cũng có vấn đề

1 Like
#8

cơ bản thuật toán nó thế, mình cũng code trên nodepad++ thôi, chưa chạy demo… với lại khá lâu rồi có đụng chạm vào c,c++ đâu

#9

image
image.png1366×768 43.3 KB

Cách của bạn có lẽ cũng gặp vấn đề giống như mình.

#10

bạn gửi all souce cho mình giúp cho nè

#11

rotation2 là phần bạn code,

#include "pch.h"
#include <iostream>
#include <string>
#include <stack>
using namespace std; 
class SinglyLinkedListNode {
public:
	int data;
	SinglyLinkedListNode *next;

	SinglyLinkedListNode(int node_data) {
		this->data = node_data;
		this->next = nullptr;
	}
};

class SinglyLinkedList {
public:
	SinglyLinkedListNode *head;
	SinglyLinkedListNode *tail;

	SinglyLinkedList() {
		this->head = nullptr;
		this->tail = nullptr;
	}

	void insert_node(int node_data) {
		SinglyLinkedListNode* node = new SinglyLinkedListNode(node_data);

		if (!this->head) {
			this->head = node;
		}
		else {
			this->tail->next = node;
		}

		this->tail = node;
	}
};

void print_singly_linked_list(SinglyLinkedListNode* node, string sep) {
	while (node) {
		cout << node->data;
		node = node->next;
		if (node) {
			cout << sep;
		}
	}
}
void swap(SinglyLinkedListNode *a, SinglyLinkedListNode *b)
{
	int temp = a->data;
	a->data = b->data;
	b->data = temp;

}

SinglyLinkedListNode* Rotation2(SinglyLinkedListNode * head, int k)
{
	SinglyLinkedListNode * headTemp = head;
	for (int i = 1; i <= k; i++) {
		SinglyLinkedListNode *firstNode = head, *penultimateNode = headTemp;
		while (penultimateNode->next->next != NULL) {
			penultimateNode = penultimateNode->next;
		}
		SinglyLinkedListNode *lastNode = penultimateNode->next;
		lastNode->next = firstNode;
		penultimateNode->next = NULL;
		headTemp = lastNode;
	}
	return headTemp;
}

void rotation(SinglyLinkedListNode*head, int k)
{
	if (head == NULL || head->next == NULL) return;


	while (k > 0)
	{
		SinglyLinkedListNode *preLast = head, *first = head;
		while (preLast->next->next)
		{
			preLast = preLast->next;
		}
		SinglyLinkedListNode *last = preLast->next;
		preLast->next = NULL;
		last->next = first;
		head = last;
		k--;


	}

}



int main()
{
	SinglyLinkedList *llist = new SinglyLinkedList();
	llist->insert_node(3);
	llist->insert_node(5);
	llist->insert_node(7);
	llist->insert_node(8);
	
	SinglyLinkedListNode* result = Rotation2(llist->head, 3);
	print_singly_linked_list(result, " ");
	return 0;
}
#12 
SinglyLinkedListNode* Rotation2(SinglyLinkedListNode* head, int k)
{
	SinglyLinkedListNode* headTemp = head;
	for (int i = 1; i <= k; i++) {
		SinglyLinkedListNode* firstNode = headTemp, * penultimateNode = headTemp;
		while (penultimateNode->next->next != NULL) {
			penultimateNode = penultimateNode->next;
		}
		SinglyLinkedListNode* lastNode = penultimateNode->next;
		lastNode->next = firstNode;
		penultimateNode->next = NULL;
		headTemp = lastNode;
	}
	return headTemp;
}

// mình chỉnh lại cái SinglyLinkedListNode* firstNode = headTemp, * penultimateNode = headTemp;

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?