Have you learned the linked list? It’s enough to know how to do these problems. The idea is all in the GIF.

Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”

This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

1. Remove linked list elements < difficulty ⭐ >

📝 : give you a linked list head Node head and an integer val, please delete all linked list nodes that meet node. val == val, and return the new head Node.

💨 Example 1:

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

Output: [1, 2, 3, 4, 5]

💨 Example 2:

Enter: head = [], val = 1

Output: []

💨 Example 3:

Enter: head = [7,7,7,7], val = 7

Output: []

🧷 Platform: Visual Studio 2017 && Windows

🔑 Core Idea:

1, double pointer, cur find the node where val is located, prev record the previous position and delete it successively.

Idea 2: New list, insert all values in the list that are not val into the new list, delete the node of val

Leetcode the original

#include<stdio.h>
#include<stdlib.h>

typedef int SLTDataType;

struct ListNode
{
	int val;
	struct ListNode *next;
};
//思路1
struct ListNode* removeElements1(struct ListNode* head, int val)
{
	struct ListNode * cur = head;
	struct ListNode * prev = NULL;
	while (cur)// Determine the address
	{
		//1
		if (cur->val == val)
		{
			if (cur == head)// if the first object is equal to val
			{
				head = head->next;
				free(cur);
				cur = head;
			}
			else// when other objects are equal to val
			{
				prev->next = cur->next;
				free(cur); cur = prev->next; }}//2
		else{ prev = cur; cur = cur->next; }}return head;

}
/ / ideas 2
struct ListNode* removeElements2(struct ListNode* head, int val)
{	
	if(head == NULL)
		return NULL;
	// Create a node
	struct ListNode* newhead = NULL, *tail = NULL;
	struct ListNode* cur = head;
	while(cur)
	{
		struct ListNode* next = cur->next;
		if(cur->val == val)
		{
			free(cur);
		}
		else
		{
			if(tail == NULL)
			{
				newhead = tail = cur;	
			}
			else
			{
				tail->next = cur;	
				tail = cur;
			}
		}
		cur = next;
	}
	if(tail)
		tail->next = NULL;
	return newhead;
}
int main(a)
{
	struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n1->val = 1;

	struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n2->val = 2;

	struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n3->val = 6;

	struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n4->val = 3;

	struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n5->val = 4;

	struct ListNode* n6 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n6->val = 5;

	struct ListNode* n7 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n7->val = 6;

	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = n5;
	n5->next = n6;
	n6->next = n7;
	n7->next = NULL;

	removeElements1(n1, 6);
	removeElements2(n1, 6);
	return 0;
}
Copy the code

2. Reverse a linked list < difficulty factor ⭐ >

📝 description: give you a single linked list of the head node head, please reverse the list, and return the reversed list.

💨 Example 1:

Enter: head = [1,2,3,4,5]

Output:,4,3,2,1 [5]

💨 Example 2:

Enter: head = [1,2]

Output: [2, 1]

💨 Example 3:

Enter: head = []

Output: []

🧷 Platform: Visual Studio 2017 && Windows

🔑 Core Idea:

Idea 1: Adjust the direction of the node pointer

Idea 2: Head plug

#include<stdio.h>
#include<stdlib.h>

typedef int SLTDataType;

struct ListNode
{
	int val;
	struct ListNode *next;
};
//思路1
struct ListNode* reverseList1(struct ListNode* head)
{
	/ / an empty list
    if(head == NULL)
        return head;
    struct ListNode* n1, *n2, *n3;
    n1 = NULL;
    n2 = head;
    n3 = head->next;

    while(n2)
    {
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        // The last time it came in, n3 was null
        if(n3)
            n3 = n3->next;
    }
    return n1;
}
/ / ideas 2
struct ListNode* reverseList2(struct ListNode* head)
{
	struct ListNode *newnode, *cur, *next;
    newnode = NULL;
    cur = head;
    while(cur)
    {
        next = cur->next;   
        cur->next = newnode;
        newnode = cur;
        cur = next;
    }
    return newnode;
}
int main(a)
{
	struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n1->val = 1;

	struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n2->val = 2;

	struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n3->val = 3;

	struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n4->val = 4;

	struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n5->val = 5;
	
	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = n5;
	n5->next = NULL;
	
	reverseList1(n1);
	reverseList2(n1);
	return 0;
}
Copy the code

3. Intermediate nodes of the linked list < difficulty coefficient ⭐ >

📝 description: Given a non-empty single linked list whose head is head, return the intermediate node of the list. If there are two intermediate nodes, the second intermediate node is returned.

💨 Example 1:

Input: [1, 2, 3, 4, 5]

Output: Node 3 in this list (serialized form: [3,4,5]) returns the value of node 3. (the evaluation system serializes the node as ([3,4,5]). Val = 3, ans.next-val = 4, ans.next-next-val = 5, and ans.next-next-next = NULL.

🧷 Platform: Visual Studio 2017 && Windows

🔑 Core Idea:

The fast pointer takes 2 steps and the slow pointer takes 1 step. When the fast pointer finishes, the current position of the slow pointer is the middle node

#include<stdio.h>
#include<stdlib.h>

typedef int SLTDataType;

struct ListNode
{
	int val;
	struct ListNode *next;
};
struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode *slow, *fast;
    slow = fast = head;
    // Both odd-even conditions must be met
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}
int main(a)
{
	struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n1->val = 1;

	struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n2->val = 2;

	struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n3->val = 3;

	struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n4->val = 4;

	struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n5->val = 5;
	
	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = n5;
	n5->next = NULL;

	middleNode(n1);
	return 0;
}
Copy the code

4. The KTH last node in the linked list < difficulty coefficient ⭐ >

📝 description: Input a linked list, output the last KTH node in the list. In order to conform to the convention of most people, this case counts from 1, i.e. the last node of the list is the last node from the last.

💨 example:

Given a linked list: 1->2->3->4->5, and k = 2.

Return to list 4->5

🧷 Platform: Visual Studio 2017 && Windows

🔑 Core Idea:

The fast pointer takes K steps first, and the difference between the fast pointer and the slow pointer is K steps. Then the fast pointer moves step by step at the same time until the fast pointer points to NULL. At this point, the node to which the slow pointer points is the target node

Leetcode the original

The original problem

I did the problem ⚠ on both platforms. According to the conventional writing method, I found that it could pass the code in LeetCode, but could not pass the code in Niuke

So we’re going to write it a little bit more strictly

#include<stdio.h>
#include<stdlib.h>

typedef int SLTDataType;

struct ListNode
{
	int val;
	struct ListNode *next;
};
struct ListNode* getKthFromEnd(struct ListNode* head, int k)
{
	if(k == 0)
        return NULL;
	struct ListNode *slow, *fast;
    slow = fast = head;
    // Take k steps first
    while(k--)
    {
		// If k is greater than the length of the list
        if(fast == NULL)
            return NULL;    
        fast = fast->next;
    }
    // Slow and fast go at the same time until FAST points to empty
    while(fast)
    {
        slow = slow->next;
        fast = fast->next;
    }
    
    return slow;
}
int main(a)
{
	struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n1->val = 1;

	struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n2->val = 2;

	struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n3->val = 3;

	struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n4->val = 4;

	struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n5->val = 5;
	
	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = n5;
	n5->next = NULL;

	getKthFromEnd(n1, 2);
	return 0;
}
Copy the code

5. Merge two ordered lists < difficulty factor ⭐ >

📝 : Merge two ascending lists into a new ascending list and return. A new list is formed by concatenating all the nodes of a given two lists.

💨 Example 1:

Input: l1 = [1,2,4], l2 = [1,3,4]

Output:,1,2,3,4,4 [1]

💨 Example 2:

Input: L1 = [], l2 = []

Output: []

💨 Example 3:

Input: L1 = [], l2 = [0]

Output: [0]

🧷 Platform: Visual Studio 2017 && Windows

🔑 Core Idea:

Idea 1, see the figure below

Idea 2, head nodes with sentries

I didn’t know what a sentinel head node is in the previous article, but here it is:

1️ sentinel head node, which does not store effective data; The non-sentinel head node stores valid data

2. If the head pointer of ️ non-sentinel head node needs to be modified, second-level pointer operation is needed; The sentinel head node, on the other hand, does not modify the head pointer because it does not store valid data

3️ sentinel head node rarely appears in practice, including hash barrel, adjacent table and substructure are not lead. Secondly, the linked list given in OJ is not the lead (as can be seen from the above problems), so we should try to use the lead in the future coding process

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>

typedef int SLTDataType;

struct ListNode
{
	int val;
	struct ListNode *next;
};
//思路1
struct ListNode* mergeTwoLists1(struct ListNode* l1, struct ListNode* l2)
{
	struct ListNode *n1 = l1, *m1 = l2;
	struct ListNode *newhead = NULL, *tail = NULL;
	// Determine the empty list
    if(l1 == NULL)
        return l2;
    if(l2 == NULL)
        return l1;
        
	while(n1 && m1)
	{
		if(n1->val < m1->val)
		{
			if(newhead == NULL)
			{
				newhead = tail = n1;
			}
			else
			{
				tail->next = n1;
				tail = n1;
			}	
			n1 = n1->next;		
		} 
		else
		{
			if(newhead == NULL)
			{
				newhead = tail = m1;
			}
			else{ tail->next = m1; tail = m1; } m1 = m1->next; }}// Link the rest of the data
    if(n1)
        tail->next = n1;
    if(m1)
        tail->next = m1;
        
    return newhead;
}
/ / ideas 2
struct ListNode* mergeTwoLists2(struct ListNode* l1, struct ListNode* l2)
{
	struct ListNode *n1 = l1, *m1 = l2;
	struct ListNode *newhead = NULL, *tail = NULL;
    // Determine the empty list
    if(l1 == NULL)
        return l2;
    if(l2 == NULL)
        return l1;
    // Request space
    newhead = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
	while(n1 && m1)
	{
		if(n1->val < m1->val)
		{
			tail->next = n1;
			tail = n1;	
			n1 = n1->next;		
		} 
		else{ tail->next = m1; tail = m1; m1 = m1->next; }}// Link the rest of the data
    if(n1)
        tail->next = n1;
    if(m1)
        tail->next = m1;
    // Return the head node with no sentry. Second, malloc opens up space, so you have to release it, or you'll leak memory
    struct ListNode* first = newhead->next;
    free(newhead);
    return first;
}
int main(a)
{
	struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n1->val = 1;

	struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n2->val = 2;

	struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n3->val = 4;

	n1->next = n2;
	n2->next = n3;
	n3->next = NULL;
	/ * -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- segmentation -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - * /
	struct ListNode* m1 = (struct ListNode*)malloc(sizeof(struct ListNode));
	m1->val = 1;

	struct ListNode* m2 = (struct ListNode*)malloc(sizeof(struct ListNode));
	m2->val = 3;

	struct ListNode* m3 = (struct ListNode*)malloc(sizeof(struct ListNode));
	m3->val = 4;

	n1->next = n2;
	n2->next = n3;
	n3->next = NULL;
	
	mergeTwoLists1(n1, m1);
	mergeTwoLists2(n1, m1);
	
	return 0;
}
Copy the code