“This is the 7th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

Small farmers presented a single – linked list to celebrate the ceremony

Defects in sequential tables

1. The space is insufficient and needs to be expanded

Realloc mechanism cost, and the body to the cost, 1. After the memory is enough to open up on the spot expansion, 2. When the memory is insufficient, it will be expanded remotely

2. Avoid frequent expansion. When we are full, we will basically expand twice, which may lead to a certain amount of space waste

3. The sequential table requires data to be stored continuously from the beginning position, so we need to move data when inserting and deleting data in the head or middle position, which is inefficient

In view of the defects of the sequential list, a linked list is designed

Linked lists claim space on demand, free space if not used (more rational use of space)

The middle and tail of the head are inserted to delete data without moving data

Of course, it also has drawbacks, such as storing a pointer at the end of each data node to link to the following data node

Random access is not supported.

The list

The concept and structure of linked lists

** Concept: ** A linked list is a physical storage structure that is non-sequential and non-sequential. The logical order of data elements is realized by linking the order of Pointers in the list

Classification of linked lists

In practice, linked list structures are very diverse, and there are eight linked list structures combined

1. Unidirectional or bidirectional

2. Lead or not

3. Cyclic or non-cyclic

Although there are so many linked list structures, the two most commonly used in practice are the two

1. Headless one-way acyclic linked list:Simple structure,It’s not usually used to store data alone. In practice it is more about doingSubstructures of other data structures, such as hash buckets, graph adjacency lists, and so on. In addition, this structure is inThe written interviewThere are many.
2. Lead bidirectional cyclic linked list:The most complex structure,Usually used to store data separately. The list data structures used in practice are all bidirectional circular lists. In addition, although the structure is complex, but the use of code implementation will find that the structure will bring many advantages, implementation instead

Simple, behind our code implementation will know.

Implementation of linked list

The headless one-way

Single-linked list nodes

typedef int SLTDataType;

// Single linked list node
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;
Copy the code

Single list printing function SListPrint

Sometimes it’s a little bit inconvenient to debug it step by step so let’s just write out the print function, and then add, delete, change and check, okay

// Single linked list printing
void SListPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while(cur ! =NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}
Copy the code

SListPushBack single-list tail-insert function

Whenever you’re inserting whatever you’re doing or whatever you’re inserting you’re going to have to expand, and of course the units of expansion for singly linked lists are nodes, right

// single linked list tail
void SListPushBack(SLTNode** pphead, SLTDataType x)
{
	// Apply for a new node
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	newnode->data = x;
	newnode->next = NULL;
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		// Find the tail node
		SLTNode* tail = *pphead;
		while(tail->next ! =NULL) { tail = tail->next; } tail->next = newnode; }}Copy the code

Get the single-linked list node function BuySListNode

At this point, I wanted to write header inserts, but after thinking about it, I realized that the node creation step would duplicate some of the steps in the tail inserts, so it would be easier to separate out the repeated steps and write them as a function

SLTNode* BuySListNode(SLTDataType x) {// apply for a newnode SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); If (newNode == NULL)// If (newNode == NULL) {printf(" application failed \n"); exit(-1); } newnode->data = x; newnode->next = NULL; return newnode; // Return the pointer to the node}Copy the code

So we can use this as a carbon copy of the tail

Single list header function SListPushFront

// single list header interpolation function
void SListPushFront(SLTNode** pphead, SLTDataType x)
{
	// Apply for a new node
	SLTNode* newnode = BuySListNode(x);
	
	// add the plist header address to the new node
	newnode->next = *pphead;
	// Then make newNode the plist head node
	*pphead = newnode;
}
Copy the code

SListPopBack is a singly linked list tail deletion function

// Delete the end of the single linked list
void SListPopBack(SLTNode** pphead)
{
	assert(*pphead);
	if(! (*pphead)->next) {free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* prev = NULL;// Similar to a marker node pointer
		SLTNode* tail = *pphead;
		while (tail->next)// Find the last node
		{
			prev = tail;// Make prev store tail before each operation
			tail = tail->next;
		}
		free(tail);// Free his space
		tail = NULL;// Then point to null
		// But the previous next we didn't do anything to point to the space that had already been freed
		prev->next = NULL; }}Copy the code

Single-linked header delete function SListPopFront

// Delete the single linked header
void SListPopFront(SLTNode** pphead)
{
	assert(*pphead);
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	(*pphead) = next;
}
Copy the code

Singly linked list lookup function

// single list lookup function
SLTNode* SListFind(SLTNode* phead,SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		else{ cur = cur->next; }}return NULL;
}
Copy the code

The way a master file is written

void test1(a)
{
	SLTNode* plist = NULL;
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPushFront(&plist, 1);
	SListPushBack(&plist, 4);
	SListPushFront(&plist, 2);
	SListPushBack(&plist, 4);
	SListPushFront(&plist, 3);
	SListPushBack(&plist, 4);
	SListPushFront(&plist, 4);
	SListPrint(plist);

	SLTNode* pos =  SListFind(plist,4);
	int i = 1;
	while (pos)
	{
		printf("%d pos node,%p->%d\n",i++,pos,pos->data);
		// Find the next address
		pos = SListFind(pos->next, 4); }}Copy the code

Modify after Query

	SLTNode* pos1 = SListFind(plist,2);
	if (pos1)
	{
		// We can see the value of the node pointer returned by the query
		pos1->data = 20;
	}
	SListPrint(plist);
Copy the code

Singly linked list insertion functions

This can be done in conjunction with the query function

// single list insertion function
// Insert pos in front of pos
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	// Create the node first
	SLTNode* newnode = BuySListNode(x);
	if (pos == *pphead)
	{
		newnode->next = *pphead;
		*pphead = newnode;
	}
	else
	{
		// Find the previous position of pos
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = newnode;
		newnode->next = pos;
	}	
}
Copy the code

If you look at the above, you know that single linked lists are not very good for insertion in the front, but it’s good for insertion in the back, because insertion in the front you have to know that the position of the node in front of the current position is a little bit complicated, and insertion in the back doesn’t have the pointer to the node in the prev

Singly linked list after interpolation function

// single list after interpolation function
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
	// Create a new node
	SLTNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
Copy the code

Single-linked list deletion function SListErase

//void SListErase(SLTNode** pphead, SLTNode* pos) //{// SLTNode* cur = *pphead; // SLTNode* prev = NULL; // while (cur) // { // if (cur == pos) // { // if (pos == *pphead) // { // cur = (*pphead)->next; // free(*pphead); // (*pphead) = NULL; // *pphead = cur; // } // else // { // prev->next = cur->next; // free(cur); // cur = prev->next; // } // } // else // { // prev = cur; // cur = cur->next; Void SListErase(SLTNode** pphead, SLTNode** pphead, SLTNode* pos) {if (pos == (*pphead)) {// SListPopFront(pphead); } else { SLTNode* prev = *pphead; while (prev->next ! = pos) { prev = prev->next; } prev->next = pos->next; free(pos); pos = NULL; }}Copy the code

And, of course, neat post-delete functions

Single linked list post delete function

// single list after delete function
void SListEraseAfter(SLTNode* pos)
{
	assert(pos->next);
	SLTNode* nextnode = pos->next;
	pos->next = nextnode->next;
	free(nextnode);
}

Copy the code

Singly linked list destruction function

// Single list destruction function
void SListDestory(SLTNode** pphead)
{
	SLTNode* cur = *pphead;
	while (cur)
	{
		SLTNode* nextnode = cur->next;
		free(cur);
		cur = nextnode;
	}
	*pphead = NULL;
}
Copy the code

Exercises (Since childhood, the teacher has always taught us that the combination of numbers and shapes is the basis of logic. Often simple things become powerful when mastered by someone, while those without intention are ignored on the way to death. I used to like to walk fast, but now I slow down my pace in order to walk far)

1.Removes a linked list element

The illustration

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

2.Reverse a linked list

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode* prev = NULL;
    struct ListNode* cur = head;
    if(! cur) {return head;
    }
    else
    {
        struct ListNode* next = head->next;
        while(next)
        {       
            cur->next = prev;
            prev = cur;
            cur = next;  
            next = next->next;     
        }   
        cur->next = prev;
        returncur; }}Copy the code

3.The middle node of a linked list

struct ListNode* middleNode(struct ListNode* head){
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while((fast ! =NULL)&&(fast->next ! =NULL))
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}
Copy the code

4.The KTH node from the bottom of the list

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    struct ListNode* fast = pListHead;
    struct ListNode* slow = pListHead;
    while(k--)
    {
        if(! fast) {return NULL;
        }
        fast = fast->next;        
    }
    while(fast)
    {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}
Copy the code

5.Merges two ordered lists

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
    struct ListNode* head = NULL;
    struct ListNode* tail = NULL;
    if(! l1)return l2;
    if(! l2)return l1;    
    while(l1&&l2)
    {
        if(l1->val <= l2->val)
        {
            if(! head) { head = tail = l1; }else
            {
                tail->next = l1;
                tail = l1;
            }
            l1 = l1->next;
        } 
        else
        {
            if(! head) { head = tail = l2; }else
            {
                tail->next = l2;
                tail = l2;
            }
            l2 = l2->next;
        }
    }
    tail->next = (l1 == NULL)? l2 : l1;return head;       
}
Copy the code

6.List segmentation

Out of the loop

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // Create two lists of sentinels
        struct ListNode* smallHead = (struct ListNode*)malloc(sizeof(struct ListNode));
        struct ListNode* largeHead = (struct ListNode*)malloc(sizeof(struct ListNode));
        struct ListNode* smallTail = smallHead;
        struct ListNode* largeTail = largeHead;
        struct ListNode* cur = pHead;
       while(cur)
       {
           if(cur->val < x)
           {
               smallTail->next = cur;
               smallTail = cur;
               // Since there is this sentence, take him below
               //cur = cur->next;
           }
           else
           {
               largeTail->next = cur;
               largeTail = cur;
              // cur = cur->next;
           }
           cur = cur->next;
       }
        // Link two lists
        smallTail->next = largeHead->next;
        largeTail->next = NULL;
        struct ListNode* newnode = smallHead->next;
        // Drop the sentry free
        free(smallHead);
        free(largeHead);
        returnnewnode; }};Copy the code

7.Palindrome structure of linked lists

So we find the first node of the reverse list, then reverse it, and then see if it’s a looped list

struct ListNode* ReversalNode(struct ListNode* phead)
{
    struct ListNode* prev = NULL;
    struct ListNode* cur = phead;
    if(! cur) {return cur;
    }
    else
    {
        struct ListNode* next = phead->next;
        while(next)
        {
            cur->next = prev;
            prev = cur;
            cur = next;  
            next = next->next;
        }
        cur->next = prev;
        returncur; }}// find the intermediate node
struct ListNode* MidNode(struct ListNode* phead)
{
    struct ListNode * fast, *slow;
    fast = slow = phead;
    while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
    return slow;
}

class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {        
        struct ListNode* curA = A;
        // Then prepare the reverse list
        struct ListNode* curR = ReversalNode(MidNode(A));
        while(curR)
        {
            if(curA->val ! = curR->val)return 0;
            curA = curA->next;
            curR = curR->next;
        }
        return true; }};Copy the code

When do you code properly: if you have an idea in mind, you can code it

When do you become good at debugging: You spend more time analyzing code than you do writing it

8.Cross linked list(This problem force buckle is a little lax consider NULL run past, do not consider instead run past)

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode * tailA = headA;
    struct ListNode * tailB = headB;
    int lenA = 0;
    int lenB = 0;
    
    while(tailA->next)
    {
        tailA = tailA->next;
        lenA++;
    }
    while(tailB->next)
    {
        tailB = tailB->next;
        lenB++;
    }
    if(tailA ! = tailB)return NULL;
    int gap = lenA>lenB ? lenA-lenB : lenB-lenA;
    // Let's suppose A is long and B is short
    struct ListNode *longList = headA;
    struct ListNode *smallList = headB;
    // The advantage of this is that we do not need to write the exact same function
    if(lenB>lenA)
    {
        longList = headB;
        smallList = headA;
    }
    while(gap--)
    {
        longList = longList->next;
    }
    while(longList ! = smallList) { longList = longList->next; smallList = smallList->next; }return longList;
}

Copy the code