首页 > 其他分享 >leetcode以及牛客网单链表相关的题、移除链表元素、链表的中间节点、合并两个有序链表、反转链表、链表分割、倒数第k个节点、链表的回文结构、相交链表、环形链表，随机链表的复制等的介绍

leetcode以及牛客网单链表相关的题、移除链表元素、链表的中间节点、合并两个有序链表、反转链表、链表分割、倒数第k个节点、链表的回文结构、相交链表、环形链表，随机链表的复制等的介绍

时间：2024-05-25 17:58:49浏览次数：12  
标签：ListNode struct next 链表 移除 NULL 节点 cur

文章目录

前言

leetcode以及牛客网单链表相关的题、移除链表元素、链表的中间节点、合并两个有序链表、反转链表、链表分割、倒数第k个节点等的介绍

一、移除链表元素

在这里插入图片描述

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {
    
    ListNode* newhead = NULL;
    ListNode* newtail = NULL;
    ListNode* cur = head;
    while(cur)
    {
        if(cur->val != val)
        {
            if(newhead == NULL)
            {
                newhead = newtail = cur;
            }
            else
            {
                newtail->next = cur;
                newtail = newtail->next;
            }
            cur = cur->next;
           
        }
        else
        {
            ListNode* next = cur->next;
            free(cur);
            cur = next;
        }
        
    }
    if(newtail)
            newtail->next = NULL;
    return newhead;
}
  • 遍历链表，若节点的值不等于给定的值，则尾插到新链表后面。
  • 若等于，则跳过。

二、链表的中间节点

在这里插入图片描述

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {
    ListNode* fast = head, *slow = head;

    while(fast != NULL && fast->next != NULL)
    {
        fast = fast->next->next;
        slow = slow->next;
    }

    return slow;

}
  • 快慢指针
  • 快指针一次走两步。
  • 慢指针一次走一步。
  • 当快指针节点为空或者下一个节点为空时，跳出循环。
  • 此时慢指针指向中间节点。

三、合并两个有序链表

在这里插入图片描述

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if(list1 == NULL &&list2 == NULL)
    {
        return NULL;
    }
    
    ListNode* newHead , *newTail;
    newHead = newTail = NULL;

    while(list1 != NULL && list2 != NULL)
    {
        if(list1->val > list2->val)
        {
            if(newHead == NULL)
            {
                newHead = newTail = list2;
            }
            else
            {
                newTail->next = list2;
                newTail = newTail->next;
            }
            list2 = list2->next;
        }
        else
        {
            if(newHead == NULL)
            {
                newHead = newTail = list1;
            }
            else
            {
                newTail->next = list1;
                newTail = newTail->next;
            }
            list1 = list1->next;
        }
    }
    if(list1 == NULL)
    {
        if(newHead == NULL)
            newHead = list2;
        else
            newTail->next = list2;
    }
    else
    {
        if(newHead == NULL)
            newHead = list1;
        else
            newTail->next = list1;
    }
    return newHead;
}
  • 遍历两个单链表。
  • 两个链表都不为空，判断节点大小，将小点节点尾插到新的头节点上。
  • 若有一个链表为空，跳出循环，并将另一个链表尾插到新的尾节点上。

四、反转链表

在这里插入图片描述

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {
    if(head == NULL)
        return NULL;
   ListNode* n1, *n2, *n3;

   n1 = NULL;
   n2 = head;
   n3 = head->next;

   while(n2)
   {
        n2->next = n1;

        n1 = n2;
        n2 = n3;
        if(n3)
            n3 = n3->next;
   }
    
    return n1;
}
    1. 将每个节点的next指向前一个节点。
    1. 创建一个新的头节点，遍历链表进行头插。

五、链表分割

在这里插入图片描述

/*
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* gGuard, *gTail, *lGuard, *lTail;

        gGuard = gTail = (struct ListNode*)malloc(sizeof(struct ListNode));
        lGuard = lTail = (struct ListNode*)malloc(sizeof(struct ListNode));
        gGuard->next = lGuard->next = NULL;

        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 = gGuard->next;
        gTail->next = NULL;
        pHead = lGuard->next;

        free(gGuard);
        free(lGuard);

        
        
        return pHead;
        

    }
};
  • 创建两个带有哨兵位的单向链表。
  • 若小于给定值尾插到小的链表中。
  • 若大于等于给定值尾插到大的链表中。
  • 再将小链表的尾节点的next指向大链表的第一个有效节点。
  • 最后再将大链表的尾节点的next指向NULL。

六、倒数第k个节点

输入一个链表，输出该链表中倒数第k个结点。

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

typedef struct ListNode
{
	int val;
	struct ListNode* next;
}ListNode;


ListNode* FindKthToTail(ListNode* pListHead, int k)
{
	if (pListHead == NULL)
	{
		return NULL;
	}
	ListNode* fast, * slow;
	fast = slow = pListHead;

	int i = 0;
	for (i = 1; i < k; i++)
	{

		fast = fast->next;
		if (fast == NULL)
		{
			return NULL;
		}
	}

	while (fast->next != NULL)
	{
		fast = fast->next;
		slow = slow->next;
	}
	return slow;
}

int main()
{

	ListNode* phead = (ListNode*)malloc(sizeof(ListNode));
	ListNode* n2 = (ListNode*)malloc(sizeof(ListNode));
	ListNode* n3 = (ListNode*)malloc(sizeof(ListNode));
	ListNode* n4 = (ListNode*)malloc(sizeof(ListNode));
	ListNode* n5 = (ListNode*)malloc(sizeof(ListNode));


	phead->val = 1;
	n2->val = 2;
	n3->val = 3;
	n4->val = 4;
	n5->val = 5;

	phead->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = n5;
	n5->next = NULL;

	ListNode* plist = phead;

	ListNode* ret = FindKthToTail(plist,5);

	while (ret)
	{
		printf("%d->", ret->val);
		ret = ret->next;
	}
	printf("NULL\n");

	return 0;
}
  • 倒数第k个和倒数第一个之间的距离是k-1.
  • 所以使用快慢指针，将快的指针先走k-1步，此时快慢指针差距是k-1.
  • 所以当快指针走到链表结尾时，慢指针走到倒数第k个节点。

七、链表的回文结构

在这里插入图片描述

/*
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 , *slow;
        fast = slow = head;

        while(fast!= NULL && fast->next!=NULL)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }

    // 逆置链表
    struct ListNode* ReverseList(struct ListNode* phead)
    {
        // struct ListNode* newHead = NULL;

        // struct ListNode* cur = phead;
        // while(cur)
        // {
        //     struct ListNode* next = cur->next;

        //     cur->next = newHead;
        //     newHead = cur;

        //     cur = next;
        // }
        // return newHead;

        struct ListNode* n1, *n2, *n3;
        n1 = NULL;
        n2 = phead;
        n3 = phead->next;

        while(n2)
        {
            n2->next = n1;

            n1 = n2;
            n2 = n3;
            if(n3)
                n3 = n3->next;
        }
        
        return n1;
    }


    bool chkPalindrome(ListNode* head) {
        // write code here

        struct ListNode* middle = MiddleNode(head);
        struct ListNode* rhead = ReverseList(head);

        while(rhead)
        {
            if(head->val != rhead->val)
                return false;
            head = head->next;
            rhead  = rhead->next;
        }

        return true;
    }
};
  • 先找到链表的中间节点。
  • 将中间节点之后直到链表末尾的节点逆置。
  • 比较head头节点开始的链表和中间节点开始的链表。
  • 若相等，则为回文结构
  • 若不相等，则不是回文结构

八、相交链表

在这里插入图片描述

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode* tailA = headA, *tailB = headB;

    int countA, countB;
    countA = countB = 0;
    while(tailA->next)
    {
        countA++;
        tailA = tailA->next;
    }

    while(tailB->next)
    {
        countB++;
        tailB = tailB->next;
    }

    // struct ListNode* none = (struct ListNode*)malloc(sizeof(struct ListNode));
    // none->val = 0;
    // none->next = NULL;
    if(tailA != tailB)
    {
        return NULL;
    }

    int sub = abs(countA - countB);

    struct ListNode* longList, *lessList;
    longList = lessList = NULL;
    if(countA < countB)
    {
        longList = headB;
        lessList = headA;
    }
    else
    {
        longList = headA;
        lessList = headB;
    }

    while(sub--)
    {
        longList = longList->next;
    }

    while(longList != lessList)
    {
        longList = longList->next;
        lessList = lessList->next;
    }

    return longList;
}
  • 遍历两个链表并同时求出两个链表的长度。
  • 长度相减，求出长度的差。
  • 将长链表先走差距步，然后两个链表同时向后遍历。
  • 若存在相等的节点，则返回。
  • 若不存在，则跳出循环返回NULL。

九、判断链表是否有环

在这里插入图片描述

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) {
    struct ListNode* fast , *slow;
    fast = slow = head;

    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow)
        {
            return true;
        }
    }
    return false;
}
  • 快慢指针，快指针一次走2步，慢指针一次走1步。
  • 每走一步，两个指针的差距会减小1
  • 所以在环形链表中，快指针会慢慢追上慢指针，直到相等，此时节点为想等的节点。
  • 若不是环形链表，快指针可能为空，并且快指针的next也会为空。

十、判断环形链表的入口点

在这里插入图片描述

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode* fast, *slow;
    fast = slow = head;

    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;

        if(fast == slow)
        {
            struct ListNode* meet = slow;
            
            while(meet != head)
            {
                meet = meet->next;
                head = head->next;
            }
            return meet;
        }
    }
    return NULL;
}

在这里插入图片描述

  • 通过数学推导得到结论

  • 若两个一次走一步的指针分别从起始点和相遇点走，两者相遇，则为入口点。

  • 另一种方法，将相遇点的next置为NULL，一个指针从相遇点的下一个点走，一个从链表起始点走。

  • 找连个链表的交点即为入口点。

十一、随机链表的复制

在这里插入图片描述

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */

struct Node* copyRandomList(struct Node* head) {
	struct Node* cur = head;

    // 插入拷贝节点
    while(cur)
    {
        struct Node* next = cur->next;

        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));

        copy->val = cur->val;
        
        cur->next = copy;
        copy->next = next;

        cur = next;
    }


    // 设置拷贝节点的random
    cur = head;
    while(cur)
    {
        struct Node* copy = cur->next;

        if(cur->random == NULL)
        {
            copy->random = NULL;
        }
        else
        {
            copy->random = cur->random->next;
        }
        cur = cur->next->next;
    }


    // 摘下copy链表，并回复原链表
    cur = head;
    struct Node* copyhead = NULL, *copytail = NULL;
    while(cur)
    {
        // 串联copy链表
        struct Node* copy = cur->next;
        struct Node* next = copy->next;

        if(copyhead == NULL)
        {
            copyhead = copytail = copy;
        }
        else
        {
            copytail->next = copy;
            copytail = copytail->next;
        }

        // 恢复原链表

        cur->next = next;
        cur = next;

    }
    return copyhead;
}

在这里插入图片描述

总结

leetcode以及牛客网单链表相关的题、移除链表元素、链表的中间节点、合并两个有序链表、反转链表、链表分割、倒数第k个节点等的介绍

标签：ListNode,struct,next,链表,移除,NULL,节点,cur
From： https://blog.csdn.net/Farewell_me/article/details/139158933

相关文章

  • 代码随想录算法训练营第十六天 | 104.二叉树的最大深度、559.n叉树的最大深度、111.二
    104.二叉树的最大深度题目链接：https://leetcode.cn/problems/maximum-depth-of-binary-tree/文档讲解：https://programmercarl.com/0104.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E5%A4%A7%E6%B7%B1%E5%BA%A6.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE......
  • PTA 6-18 循环链表的追加
    单链表的结点存储结构如下所示:structNode{intdata;structNode*next;};请编写函数，将一个构造好的新结点p（结点地址），添加到指针rear指向的循环单链表的尾部（rear指向的是循环单链表尾的地址,循环单链表无附加头结点），并确保rear始终指向最后一个结点（如果有的话）。函数接口定......
  • 基于节点分层的配网潮流前推回代方法【IEEE33节点】（Matlab代码实现）
     ......
  • Day3 | 203.移除链表元素 、707.设计链表 、 206.反转链表
    203.移除链表元素建议：本题最关键是要理解虚拟头结点的使用技巧，这个对链表题目很重要。题目链接/文章讲解/视频讲解：：https://programmercarl.com/0203.移除链表元素.html思考设置一个虚拟的dummy节点，方便代码逻辑一致，不然要专门处理头节点。定义一个pre节点，作为cur节点的前驱......
  • QTreeView中item节点任意拖拽移动，添加，删除与自绘指示器
    文章目录效果图主要功能点概要遇到的问题指示器拖拽总结效果图主要功能点节点自由拖拽移动自绘树的指示器可拖拽添加节点概要整体还是对于model-view这一套的使用，左侧的实现可看我的这篇文章，本文具体讲讲这个树QTreeView的拖拽与自绘指示器。关于树......
  • 算法随想录打卡第三天|链表
    //203移除链表元素publicListNoderemoveElements(ListNodehead,intval){//创建虚拟头指针不对//ListNoderes=head;//创建一个虚拟头结点ListNoderes=newListNode(val-1);res.next=head;ListNodeprev=res;......
  • DOM【事件、操作节点、DOM案例】--学习JavaEE的day49
    day49JS核心技术DOM继day48事件键盘事件监听器：onkeydown、onkeypress、onkeyup<!DOCTYPEhtml><html> <head> <metacharset="UTF-8"> <title></title> </head> <body> <inputtype="text"......
  • 代码随想录算法训练营第一天 | 704.二分查找；27. 移除元素
    代码随想录算法训练营第一天|704.二分查找（红蓝模板法）；27.移除元素（双指针法）704题链接：https://leetcode.cn/problems/binary-search/description/二分查找：https://programmercarl.com/0704.二分查找.html#其他语言版本二分查找红蓝法笔记：二分查找为什么总是写错？_哔哩哔哩_bil......
  • 23. 合并 K 个升序链表
    题目描述给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。解题思路这个题目显然是可以用归并排序（区间内单调）的方法——最核心的地方就是合并两个有序链表（力扣第21）同时也可以用优先级队列的方法，不过要修改比较方法（仿函......
  • 5.23链表相交
    链接如下：https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/solutions/1395092/lian-biao-xiang-jiao-by-leetcode-solutio-2kne/这道题比较简单，暴力循环就可以结束，但是看官方题解还是有些技巧在的，索性也就记录一下。先说下我自己的思路，我自己的思路就是类似......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99