Linked list related interview questions

Structure

typedef int T;

typedef struct Node {
    
	T data;
	Node* next;
}*node;
typedef struct Node *LinkList;

1. The inverse of a single linked list

Node* Reverse(Node *Head)// The inverse of a single linked list 
{
    
	Node *p, *q, *r;
	p = Head;
	q = NULL;
	r = NULL;
	while (p)
	{
    
		q = p->next;
		p->next = r;
		r = p;
		p = q;
	}
	return r;
}

2. Judge whether there is a ring

bool IsCircleList1(LinkList L)
{
    
	LinkList p = L;
	LinkList q = L;
	while (p->next != NULL&&q->next != NULL)
	{
    
		p = p->next;
		q = q->next->next;
		if (p == q&&q != NULL)
			return true;
		if (q == NULL&&p != NULL)
			return false;
	}
	return false;
}

bool IsCircleList2(LinkList L)
{
    
	LinkList p = L;
	LinkList q = L;
	while (p != NULL&&q != NULL)
	{
    
		p = p->next;
		q = q->next->next;
		if (p == q)
			break;
	}
	if (p == q&&q != NULL)
		return true;
	return false;
}

3. Judge the length of the ring

int GetCircleLen(LinkList L)
{
    
	LinkList p = L;
	LinkList q = L;
	while (p != NULL&&q != NULL)
	{
    
		p = p->next;
		q = q->next->next;
		if (p == q)
			break;
	}
	int count = 1;
	while (p != q->next)
	{
    
		q = q->next;
		count++;	
	}
	return count;
}

4. Judge the position of the ring

LinkList GetCirclePos(LinkList L)
{
    
	LinkList p, q;
	p = L;
	q = L;
	while (p != NULL&&q != NULL)
	{
    
		p = p->next;
		q = q->next->next;
		if (p == q)
			break;
	}
	if (p == q&&p != NULL&&p->next != NULL)
	{
    
		q = L;
		while (p != q)
		{
    
			p = p->next;
			q = q->next;
		}
		return p;
	}
	else return NULL;
}

5. Judge 2 Whether the two single linked lists intersect

bool IsInterseList(LinkList L1, LinkList L2)
{
    
	LinkList p, q;
	p = L1;
	q = L2;
	if (p == NULL || q == NULL)
		return false;
	while (p->next != NULL)
		p = p->next;
	while (q->next != NULL)
		q = q->next;
	if (p == q)
		return true;
	return false;
}

6. Determine whether the two tables intersect , Find the first point of intersection

int ListLength(LinkList L)// Chain length 
{
    
	int i = 0;
	LinkList p = L->next;
	while (p)
	{
    
		i++;
		p = p->next;
	}
	return i;
}

LinkList GetIntersePos(LinkList L1, LinkList L2)
{
    
	if (!(IsInterseList(L1, L2)))
		return NULL;
	
	int len1 = ListLength(L1);
	int len2 = ListLength(L2);

	LinkList p, q;
	
	int step = len1 - len2;
	if (step < 0)
	{
    
		step = 0 - step;
		q = L1;
		p = L2;
	}
	else{
    
		p = L1;
		q = L2;
	}
	for (int i = 0; i < step; i++)
	{
    
		p = p->next;
	}
	while (p != q)
	{
    
		p = p->next;
		q = q->next;
	}
	return p;
}

7. Only one node in the single linked list is given p( Not the last node , namely p->next!=NULL) The pointer , Delete the node .

void deleteNode(LinkList del)
{
    
	LinkList p;
	
	p = del->next;
	del->data = p->data;
	del->next = p->next;
	free(p);
}

8. Only one node in the single linked list is given p( Non empty node ), stay p Insert a node in front .

void interNode(Node* p, T val)
{
    
	Node* newnode = (Node*)malloc(sizeof(Node));
	newnode->next = p->next;
	p->next = newnode;
	newnode->data = p->data;
	p->data = val;
}

9.// Look for the last K Nodes

LinkList FindBottomNode(LinkList L, int k)
{
    
	if (L == NULL || k == 0)
		return NULL;
	
	LinkList head = L;
	LinkList behind = L;
	
	for (int i = 0; i < k - 1; i++)
	{
    
		if (head->next == NULL)
			return NULL;
		head = head->next;
	}

	while (head->next != NULL)
	{
    
		head = head->next;
		behind = behind->next;
	}
	return behind;
}

10. Given the single chain header node , Delete the last... In the list k Nodes .

void deleteNode(LinkList L,int k)
{
    
	if (L == NULL || k == 0)
		return ;

	LinkList head = L;
	LinkList behind = L;
	LinkList ptr = NULL;
	for (int i = 0; i < k - 1; i++)
	{
    
		if (head->next == NULL)
			return;
		head = head->next;
	}

	while (head->next != NULL)
	{
    
		head = head->next;
		behind = behind->next;
	}
	ptr = behind->next;
	behind->data = ptr->data;
	behind = ptr->next;
	
	free(behind);
}