• 【数据结构初阶】链表OJ

    链表OJ

    题目一：移除链表元素

    OJ
    在这里插入图片描述
    方案一：

    题目解析：
    在这里插入图片描述

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34

    方案二：

    题目解析：把原链表遍历一遍，插入新链表
    在这里插入图片描述

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31

    题目二：反转链表

    OJ
    外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

    题目解析：
    在这里插入图片描述

    代码演示：
struct ListNode
{
    int val;
    struct ListNode* next;
};
struct ListNode* reverseList(struct ListNode* head) 
{
    struct ListNode* newnode = NULL, * cur = head;
    while (cur)
    {
        struct ListNode* next = cur->next;
        //尾插
        cur->next = newnode;
        newnode = cur;
        cur = next;
    }
    return newnode;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    题目三：链表的中间节点

    OJ
    在这里插入图片描述

    题目解析：
    在这里插入图片描述

    代码演示：
struct ListNode 
{
    int val;
    struct ListNode* next;
};
struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode* fast = head, * slow = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    题目四：链表中倒数第k个结点

    OJ
    在这里插入图片描述

    题目解析：
    在这里插入图片描述

    代码演示：
struct ListNode
{
    int val;
    struct ListNode* next;
};
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k) 
{
    struct ListNode* fast = pListHead, * slow = pListHead;
    while (k--)
    {
        if (fast == NULL)
            return NULL;
        fast = fast->next;
    }
    while (fast)
    {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    题目五：合并两个有序链表

    OJ
    在这里插入图片描述

    题目解析：
    在这里插入图片描述

    代码演示：
struct ListNode 
{
    int val;
    struct ListNode* next;
};
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{
    if (list1 == NULL)
        return list2;
    if (list2 = NULL)
        return list1;
    struct ListNode* tail = NULL, * head = NULL;
    head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
    while (list1 && list2)
    {
        if (list1->val < list2->val)
        {
            tail->next = list1;
            tail = tail->next;
            list1 = list1->next;
        }
        else
        {
            tail->next = list2;
            tail = tail->next;
            list2 = list2->next;
        }
    }
    if (list1)
        tail->next = list1;
    if (list2)
        tail->next = list2;
    struct ListNode* del = head;
    head = head->next;
    free(del);
    return head;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38

    题目六：链表分割

    OJ
    在这里插入图片描述

    题目解析：
    在这里插入图片描述

    代码演示：
struct ListNode 
{
    int val;
    struct ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
}; 
class Partition
{
public:
    ListNode* partition(ListNode* pHead, int x) 
    {
        struct ListNode* lhead, * ltail, * gtail, * ghead;
        ghead = gtail = (struct ListNode*)malloc(sizeof(struct ListNode));
        lhead = ltail = (struct ListNode*)malloc(sizeof(struct ListNode));
        struct ListNode* cur = pHead;
        while (cur)
        {
            if (cur->val < x)
            {
                ltail->next = cur;
                ltail = ltail->next;
            }
            else
            {
                gtail->next = cur;
                gtail = gtail->next;
            }
            cur = cur->next;
        }
        ltail->next = ghead->next;
        gtail->next = NULL;
        struct ListNode* head = lhead->next;
        free(lhead);
        free(ghead);
        return head;
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38

    题目七：链表的回文结构

    OJ
    在这里插入图片描述

    题目解析：
    在这里插入图片描述

    代码演示：
struct ListNode 
{
	int val;
	struct ListNode* next;
	ListNode(int x) : val(x), next(NULL) {}
}; 
class PalindromeList
{
public:
	struct ListNode* middleNode(struct ListNode* head)
	{
		struct ListNode* fast = head, * slow = head;
		while (fast && fast->next)
		{
			slow = slow->next;
			fast = fast->next->next;
		}
		return slow;
	}
	struct ListNode* reverseList(struct ListNode* head)
	{
		struct ListNode* newnode = NULL, * cur = head;
		while (cur)
		{
			struct ListNode* next = cur->next;
			cur->next = newnode;
			newnode = cur;
			cur = next;
		}
		return newnode;
	}
	bool chkPalindrome(ListNode* A)
	{
		struct ListNode* mid = middleNode(A);
		struct ListNode* rmid = reverseList(mid);
		while (A && rmid)
		{
			if (A->val != rmid->val)
				return false;
			A = A->next;
			rmid = rmid->next;
		}
		return true;
	}
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46

    题目八：相交链表

    OJ
    在这里插入图片描述

    题目解析：
    定义快慢指针，使快指针先走与慢指针同步。然后同时走看是否相交
    在这里插入图片描述

    代码演示：
struct ListNode
{

    int val;
    struct ListNode* next;
};
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) 
{
    struct ListNode* curA = headA, * curB = headB;
    int lenA = 1, lenB = 1;
    while (curA)
    {
        curA = curA->next;
        lenA++;
    }
    while (curB)
    {
        curB = curB->next;
        lenB++;
    }
    if (curA != curB)
        return false;
    int gab = abs(lenA - lenB);
    struct ListNode* longest = headA, * shortest = headB;
    if (lenA < lenB)
    {
        longest = headB;
        shortest = headA;
    }
    while (gab--)
    {
        longest = longest->next;
    }
    while (shortest != longest)
    {
        
        shortest = shortest->next;
        longest = longest->next;
    }
    return longest;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42

    题目九：环形链表

    OJ

    在这里插入图片描述

    题目解析：
    在这里插入图片描述

    代码演示：
struct ListNode {
    int val;
    struct ListNode* next;
};
bool hasCycle(struct ListNode* head)
{
    struct ListNode* fast = head, * slow = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
            return true;
    }
    return false;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    题目十：环形链表II

    OJ
    在这里插入图片描述

    题目解析：
    在这里插入图片描述

    代码演示：
struct ListNode
{
    int val;
    struct ListNode* next;
};
struct ListNode* detectCycle(struct ListNode* head)
{
    struct ListNode* fast = head, * slow = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
        {
            struct ListNode* meet = slow;
            while(meet != head)
            {
                head = head->next;
                meet = meet->next;
            }
            return meet;
        }
    }
    return NULL;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26

    💘不知不觉，【数据结构初阶】链表OJ以告一段落。通读全文的你肯定收获满满，让我们继续为数据结构学习共同奋进!!!

  • 相关阅读:
    线程重用问题--ThreadLocal数据错乱
    在Bender对偶算法的时候出现bilinear项怎么办？
    SpringBoot-调用外部接口（三种方式）
    2022Vue经典面试题及答案汇总(持续更新）
    CRC校验（模型、手算、程序编写）
    「PCB智能生产」MES系统在设备管理中的应用
    如何让文字变成语音？推荐三个免费把文字变成音频软件
    【基本算法题-2022.7.26】4. 起床困难综合症
    Neo4J超详细专题教程，快来收藏起来吧
    电机保护器究竟该怎么选择
  • 原文地址：https://blog.csdn.net/2201_75642960/article/details/134328635