I just implemented a XOR linked list:


#include <stdio.h>
#include <malloc.h>
#include <memory>

struct node
{
	int val = 0;
	struct node* next = NULL;
};

void singleToDouble(struct node* head, struct node** tail)
{
	struct node* pre = head;
	struct node* post;
	if (head) post = head->next;
	else return;

	while (post)
	{
		struct node* postNext = post->next;
		post->next = (node*)((int)(pre) ^ (int)(postNext));
		pre = post;
		post = postNext;
 	}

	*tail = pre;
}

void printTailToHead(struct node* tail)
{
	printf("Tail to Head: ");
	struct node* tailPtr = tail;
	printf("%d ", tailPtr->val);
	struct node* prevPtr = tail->next;

	while (prevPtr)
	{
		printf("%d ", prevPtr->val);
		struct node* prevPrev = (node*)((int)tailPtr ^ (int)prevPtr->next);
		tailPtr = prevPtr;
		prevPtr = prevPrev;
	}
	printf("\n");
}

void printHeadToTail(struct node* head)
{
	printf("Head to Tail: ");
	struct node* headPtr = head;
	printf("%d ", headPtr->val);
	struct node* nextPtr = headPtr->next;

	while (nextPtr)
	{
		printf("%d ", nextPtr->val);
		struct node* nextNext = (node*)((int)headPtr ^ (int)nextPtr->next);
		headPtr = nextPtr;
		nextPtr = nextNext;
	}
	printf("\n");
}

void main()
{
	struct node* head = (node*)malloc(sizeof(node));
	head->val = 0;
	head->next = NULL;

	struct node* ptr = head;
	for (int i = 1; i < 10; ++i)
	{
		struct node* m_node = (node*)malloc(sizeof(node));
		m_node->val = i;
		m_node->next = NULL;
		ptr->next = m_node;
		ptr = m_node;
	}
	struct node* tail;
	singleToDouble(head, &tail);
	printTailToHead(tail);
	printHeadToTail(head);

	struct node* headNext = head->next;

	while (headNext)
	{
		struct node* nextNext = (node*)((int)head ^ (int)headNext->next);
		free(head);
		head = headNext;
		headNext = nextNext;
	}
	system("pause");
}

Leave a Reply

Your email address will not be published. Required fields are marked *