catalogue

1, Key points of this chapter

2, Introduction to linked list

3, Implementation of common interfaces for headless one-way acyclic linked list

3.1 dynamically apply for a node

3.2 single linked list printing

3.3 single chain table tail insertion

3.4 head insertion of single chain table

3.5 tail deletion of single linked list

3.6 deletion of single chain header

3.7 single linked list lookup

3.8 single linked list insert x before pos position

3.9 deleting nodes at pos position in single linked list

4, Online oj training

4.1 remove linked list elements (force buckle)

1, Key points of this chapter

1. Introduction to headless one-way acyclic linked list
2. Implementation of common interfaces for headless one-way acyclic linked list
3. Online oj training

2, Introduction to linked list

Concept: linked list is a non continuous and non sequential storage structure in physical storage structure. The logical order of data elements is through linked list
Pointer link order in.

Simply put: a linked list is a list of structures associated with each other, and the means of association is a pointer. By storing the address of the next structure, you can access the data in the structure one by one.

Compared to the sequence table. Linked list can solve some shortcomings of sequential list.

1. From the perspective of memory: both static sequential table and dynamic sequential table will have a certain memory waste. The linked list uses one node to apply for one node without memory waste.
2. From the perspective of efficiency: the sequence table moves data whether it is header insertion or intermediate insertion and deletion, and the time complexity is O (N). The linked list can be inserted and deleted as long as the pointer is changed.

 

There are 8 kinds of actual linked list structures to be combined:

1. Unidirectional and bidirectional
2. Take the lead or not
3. Circulation and non circulation

take the lead:

There is a sentinel node, which does not store any valid data and belongs to an invalid node. However, using this invalid node as the head node will have some advantages in some aspects.

For example, when you insert a new node, you don't need to pass the secondary pointer, because our head node always points to this invalid node.

One way acyclic linked list

Two way:

It means that there is no longer only one pointer in the node, but two pointers, one pointing to the previous node and the other pointing to the next node.

Headless bidirectional acyclic linked list

Cycle:

The tail pointer no longer points to NULL, but to the head node.  

Headless one-way circular linked list

 

3, Implementation of common interfaces for headless one-way acyclic linked list

3.1 dynamically apply for a node

SLTNode* BuySListNode(SLDataType x)
{
	SLTNode* newnode = malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

3.2 single linked list printing

void SListPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

3.3 single chain table tail insertion

void SListPushBack(SLTNode** pphead, SLDataType x)
{
	if (*pphead==NULL)
	{
		*pphead = BuySListNode(x);
		return;
	}
	else
	{
		SLTNode* tail;
		tail = *pphead;
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = BuySListNode(x);
		return;
	}
}

3.4 head insertion of single chain table

void SListPushFront(SLTNode** pphead, SLDataType x)
{
	SLTNode* newnode = BuySListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

3.5 tail deletion of single linked list

void SListPopBack(SLTNode** pphead)
{
	if (*pphead == NULL)
	{
		return;
	}
	else if((*pphead)->next==NULL)
	{
		*pphead = NULL;
	}
	else
	{
		SLTNode* prev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;
	}
}

3.6 deletion of single chain header

void SListPopFront(SLTNode** pphead)
{
	if (*pphead == NULL)
	{
		return;
	}
	else
	{
		SLTNode* temp = *pphead;
		(*pphead) = (*pphead)->next;
		free(temp);
	}
}

3.7 single linked list lookup

SLTNode* SListSearch(SLTNode* phead, SLDataType x)
{
	while (phead)
	{
		if (phead->data == x)
		{
			return phead;
		}
		phead = phead->next;
	}
	return NULL;
}

3.8 single linked list insert x before pos position

void SListInsert(SLTNode** pphead, SLTNode* pos, SLDataType x)
{
	SLTNode* newnode = BuySListNode(x);
	if (*pphead == NULL)
	{
		return;
	}
	else if(*pphead==pos)
	{
		newnode->next = pos;
		*pphead = newnode;
	}
	else
	{
		SLTNode* cur = *pphead;
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		newnode->next = pos;
		cur->next = newnode;
	}
}

3.9 deleting nodes at pos position in single linked list
 

void SListErase(SLTNode** phead, SLTNode* pos)
{
	if (*phead == NULL)
	{
		return;
	}
	else if (*phead == pos)
	{
		*phead == NULL;
	}
	else
	{
		SLTNode* cur = *phead;
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		cur->next = pos->next;
		free(pos);
	}
}

4, Online oj training

4.1 remove linked list elements (force buckle)

Give you a head node ， head ， and an integer ， val of the linked list. Please delete all ， nodes in the linked list val = = val's node and returns a new header node.

Input: head = [1,2,6,3,4,5,6], val = 6
 Output: [1,2,3,4,5]

Input: head = [7,7,7,7], val = 7
 Output: []

Idea:

Before and after pointers (attendant pointers), the initial state transition prev points to NULL and cur points to head. If cur - > Val = = val

Delete. The deletion steps are prev - > next = = cur - > next; cur=cur->next. The iterative process is: prev = cur, cur = = cur - > next.

In special cases, if the val to be deleted is the head node, the deletion steps are head = cur - > next; free(cur); cur=head.

Code reference:

typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val)
{
    ListNode* cur=head;
    ListNode* prev=NULL;
    while(cur)
    {
        if(cur->val==val)
        {
            if(cur==head)
            {
                head=cur->next;
                free(cur);
                cur=head;
            }
            else
            {
                 prev->next=cur->next;
                 cur=cur->next;
            }
        }
        else
        {
            prev=cur;
            cur=cur->next;
        }
    }
    return head;
}

4.2Reverse linked list (force buckle)

Give you the head node # head of the single linked list. Please reverse the linked list and return the reversed linked list.

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Input: head = []
Output: []

Here is a header insertion idea: newhead=NULL, insert the data in the head into the newhead linked list from left to right.

typedef struct ListNode ListNode; 
struct ListNode* reverseList(struct ListNode* head)
{
    ListNode* newhead=NULL;
    ListNode* cur=head;
    if(cur==NULL)
    {
        return cur;
    }
    ListNode* next=cur->next;
    while(cur)
    {
        cur->next=newhead;
        newhead=cur;
        cur=next;
        if(next)
        next=next->next;
    }
    return newhead;
}

Note: the end condition is cur==NULL; At this time, if next moves backward, next = next - > next; NULL dereference will occur.

Secondly, consider the problem of cur==NULL. Otherwise, listnode * next = cur - > next is also a dereference to null pointers.

In fact, it can be reduced to:

struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* cur = head;
    struct ListNode* newhead = NULL;
    while(cur)
    {
       struct ListNode* next = cur->next;
        cur->next = newhead;
        newhead = cur;
        cur = next; 
    }
    return newhead;
}