特价网站建设官网,网站在线生成app,中国建设银行官网入口,上海网站架设文章目录 写在前面链表OJ调试技巧移除链表元素反转链表链表的中间节点链表中倒数第K个节点链表分割问题 写在前面
本篇为本人学习链表的过程中遇到的典型OJ题#xff0c;于是整理出来分享思路和便于后续重新学习#xff0c;每个标题均可跳转至对应习题#xff0c;大多为Lee… 文章目录 写在前面链表OJ调试技巧移除链表元素反转链表链表的中间节点链表中倒数第K个节点链表分割问题 写在前面
本篇为本人学习链表的过程中遇到的典型OJ题于是整理出来分享思路和便于后续重新学习每个标题均可跳转至对应习题大多为Leetcode 链表OJ调试技巧
Leetcode中只能看到函数体不能看到链表的具体情况因此调试存在困难自己搭建链表又过于繁琐这里介绍一种很方便的链表调试技巧
原理如下
#include stdio.h
#include stdlib.h
#include assert.hstruct ListNode
{int val;struct ListNode* next;
};int main()
{struct ListNode* n1 (struct ListNode*)malloc(sizeof(struct ListNode));assert(n1);struct ListNode* n2 (struct ListNode*)malloc(sizeof(struct ListNode));assert(n2);struct ListNode* n3 (struct ListNode*)malloc(sizeof(struct ListNode));assert(n3);struct ListNode* n4 (struct ListNode*)malloc(sizeof(struct ListNode));assert(n4);struct ListNode* n5 (struct ListNode*)malloc(sizeof(struct ListNode));assert(n5);n1-val 1;n2-val 2;n3-val 3;n4-val 4;n5-val 5;n1-next n2;n2-next n3;n3-next n4;n4-next n5;n5-next NULL;
}我们只需要创建出每一个节点接着把这些节点都连在一起手动创建一个链表链表中需要多少个元素自己搭建这样可以便于调试解决OJ中遇到的问题~~ 介绍完调试的方法正式总结链表中的OJ题目 移除链表元素
给你一个链表的头节点 head 和一个整数 val 请你删除链表中所有满足 Node.val val 的节点并返回 新的头节点 1.遍历是val的删掉
一种暴力解决的方法图示如下 代码实现如下
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* prevNULL;struct ListNode* curhead;while(cur){if(cur-valval){if(prev){prev-nextcur-next;free(cur);curprev-next;}else{curhead-next;free(head);headcur;}}else{prevcur;curcur-next;}}return head;
}2.遍历链表把不是val的拿下来尾插
图解过程如下 代码如下所示
struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* curhead;struct ListNode* newnode NULL;struct ListNode* tail NULL;while(cur){if(cur-val!val){if(tailNULL){newnodetailcur;}else{tail-nextcur;tailtail-next;}curcur-next;}else{struct ListNode* delcur;curcur-next;free(del);}}if(tail)tail-nextNULL;return newnode;
}反转链表
给你单链表的头节点 head 请你反转链表并返回反转后的链表
输入head [1,2,3,4,5] 输出[5,4,3,2,1] 下面介绍两种思路均能解决问题
1.改变节点指向 定义三个节点(思考为什么定义三个而不是两个)而后通过指针遍历把cur指向的节点方向指向前一个然后通过迭代到末尾当cur为空退出循环
代码实现如下
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/struct ListNode* reverseList(struct ListNode* head)
{if(headNULL)return NULL;struct ListNode* prevNULL;struct ListNode* curhead;struct ListNode* nexthead-next;while(cur){cur-nextprev;prevcur;curnext;if(next)nextnext-next;}return prev;
}2.将每一个节点都头插
是一个新方法只需要把新创建一个头然后把每一个节点都头插进来即可下面为原理图 代码实现如下
struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* cur head;struct ListNode* rhead NULL;while (cur){struct ListNode* next cur-next;//头插cur-next rhead;rhead cur;//迭代cur next;}return rhead;
}关于代码简洁性
代码简洁程度取决于特殊情况的处理例如假设这里把next定义在while循环外那么假设参数为NULL就需要对特殊情况做处理此时代码就多了if条件整体来说简洁程度就降低了
简洁程度需要对特殊情况的处理足够好才能足够精炼解决问题 链表的中间节点
给你单链表的头结点 head 请你找出并返回链表的中间结点。 如果有两个中间结点则返回第二个中间结点。 1.遍历链表求长度
代码实现如下
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* plisthead;int flag0;while(plist){while(plist-next!NULL){plistplist-next;flag;}break;}flag1;flagflag/21;for(int i1;iflag;i){headhead-next;}return head;
}2.快慢指针法
定义两个指针一个指针是慢指针每次走一步一个指针是快指针每次走两步。当快指针走到末尾时慢指针走的位置恰好为整个链表的一半
相比起思路1来说时间复杂度只是O(N)从时间复杂度来讲这个方法更优
具体实现原理如下图所示 代码实现如下
struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* slowhead;struct ListNode* fasthead;while(fast!NULL fast-next!NULL){slowslow-next;fastfast-next-next;}return slow;
}链表中倒数第K个节点
描述 输入一个链表输出该链表中倒数第k个结点。 输入1,{1,2,3,4,5} 输出{5} 1.遍历求长度根据k求结果
代码思路和上题十分类似十分简单
/*** struct ListNode {* int val;* struct ListNode *next;* };*//*** * param pListHead ListNode类 * param k int整型 * return ListNode类*/
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {// write code herestruct ListNode* curpListHead;struct ListNode* prevpListHead;int flag0;while(cur){curcur-next;flag;}if(kflag){return NULL;}for(int i0;iflag-k;i){prevprev-next;}return prev;
}2.仿照上题快慢指针的方法解决
和上题相比略有不同的一点是上面的快指针每次走的是一样的而对于这个题来说假设K4那么就令快指针每次走四格其余思路和上题类似
总结原理这里既然要求的是倒数第k个那么就令fast指针和slow指针之间差k个然后两个一起走当fast指针到末尾的时候slow所在的位置就是fast位置减去它们一开始的距离差也就是倒数k个的位置
整体思路是十分巧妙的其实原理和方法1类似都是找到最后一个元素然后再找前面倒数的元素但相比起来使用快慢指针的方法可以让时间复杂度缩短到最少
代码实现如下
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {struct ListNode* fastpListHead;struct ListNode* slowpListHead;for(int i0;ik;i){if(fast)fastfast-next;elsereturn NULL;}while(fast){fastfast-next;slowslow-next;}return slow;
}这里思考 第一次走k步和走k-1步有什么区别 链表分割问题
题目描述 现有一链表的头指针 ListNode* pHead给一定值x编写一段代码将所有小于x的结点排在其余结点之前且不能改变原来的数据顺序返回重新排列后的链表的头指针
由于题目描述中提到不能改变原来的数据顺序那么也就意味着只能尾插因为尾插不会破坏数据顺序
于是我们要做的实际上就是把小于val的单独拿出来大于等于val的单独拿出来创建两个节点让拿出来的这两份数据分别进行尾插最后再实现链表的合并即可解决这个问题
代码的实现也相对简单代码实现如下
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {// write code herestruct ListNode* lesshead,*lesstail,*greaterhead,*greatertail;lessheadlesstail(struct ListNode*)malloc(sizeof(struct ListNode));greaterheadgreatertail(struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* curpHead;while(cur){if(cur-valx){lesstail-nextcur;lesstaillesstail-next;}else {greatertail-nextcur;greatertailgreatertail-next;}curcur-next;}//链表合并lesstail-nextgreaterhead-next;greatertail-nextNULL;pHeadlesshead-next;free(lesshead);free(greaterhead);return pHead;}
};
