devbox
天景科技苑
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【数据结构初阶】链表OJ

作者：天景科技苑 | 2024-07-22 05:18:11

赞

踩

【数据结构初阶】链表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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/天景科技苑/article/detail/863661
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。