免费分销系统一键生成,怎么做网站图片seo,佛山网站设计案例,网站建设项目安排计划表目录 1. 移除链表元素2. 反转链表3. 返回中间结点4. 返回倒数第k个结点5. 合并两个有序链表6. 分割链表7. 回文链表8. 找相交链表的公共结点9. 判断链表是否有环10. 返回链表环的入口 老铁们好#xff0c;学习完链表这个数据结构之后#xff0c;怎么能少了OJ题呢#xff1f;… 目录 1. 移除链表元素2. 反转链表3. 返回中间结点4. 返回倒数第k个结点5. 合并两个有序链表6. 分割链表7. 回文链表8. 找相交链表的公共结点9. 判断链表是否有环10. 返回链表环的入口 老铁们好学习完链表这个数据结构之后怎么能少了OJ题呢今天它来了
1. 移除链表元素 题目链接移除链表元素 题目要求 删除链表中所有值为val的结点 解题思路 拿题目的实例1举例链表可能出现前面的结点的值全是6的情况也可能整个链表的结点值都是6如图。所以删除前先处理掉前面部分 怎么处理嘞很简单让头结点head一直往后走就行了如果head为空了就返回 情况1 情况2 处理完前面部分就可以开始删除了因为处理了前面部分所以此时head的值一定不是val所以初始状态定义cur指向链表的第二个结点prev指向第一个结点cur用于遍历链表prev则保存了cur的前一个结点的位置当cur结点的值为val时让prev的next指向cur的next即可如图 代码
class Solution {public ListNode removeElements(ListNode head, int val) {if (head null) {return null;}// 处理前面部分while (head.val val) {head head.next;if (head null) {return head;}}ListNode prev head;ListNode cur head.next;while (cur ! null) {if (cur.val val) {prev.next cur.next;} else {prev cur;}cur cur.next;}return head;}
}2. 反转链表 题目链接反转链表 题目要求 将原来的链表反转返回新链表的头结点 解题思路 如图注意箭头的方向遍历链表每遍历一个结点就让当前的结点的next指向前一个结点(头插法)接着更新head。遍历前不要忘了把第一个结点的next置空因为反转后第一个结点变成最后一个结点最后一个结点的next值应该是null
代码
class Solution {public ListNode reverseList(ListNode head) {if(headnull) {return head;}ListNode cur head.next;head.next null;while(cur!null) {ListNode next cur.next;cur.next head;head cur;cur next;}return head;}
}3. 返回中间结点 题目链接链表的中间结点 题目要求 返回链表的中间结点如果中间结点有两个返回第二个结点 解题思路 快慢指针定义一个fast指针和slow指针fast和slow的起点相同都是指向第一个结点每次让fast向后移动两步slow向后移动一步当fast指向最后一个结点时slow指向的刚好是中间结点 原理 让两个人在同一起跑点开始跑步直线运动一个人的速度是另一个人的两倍时间相同的情况下速度快的人跑完全程速度慢的人的路程刚好是全程的一半 中间结点只有一个的情况 中间结点有两个的情况
代码
class Solution {public ListNode middleNode(ListNode head) {if(head null) {return null;}ListNode fast head;ListNode slow head;while(fast!nullfast.next!null) {fast fast.next.next;slow slow.next;}return slow;}
}4. 返回倒数第k个结点 题目链接返回倒数第k个结点 题目要求 返回倒数第k个结点的val值给定的k保证是有效的 解题思路 快慢指针让快的指针先走完倒数第k个与最后一个结点的差值走k-1步然后快慢指针一起走 代码
class Solution {public int kthToLast(ListNode head, int k) {ListNode fast head;ListNode slow head;//快指针先走k-1步for(int i 0;ik-1;i) {fast fast.next;}//一起走while(fast.next!null) {//fast fast.next;slow slow.next;}return slow.val;}
}5. 合并两个有序链表 题目链接合并两个有序链表 题目要求 将两个升序的链表合并为一个升序的链表 解题思路 定义新的结点newHead表示新链表的头结点再定义newTail表示新链表的尾结点定义l1、l2用于遍历原来的两个链表比较l1、l2结点的值将小的值的结点给新的链表重复这个操作如果l1遍历结束newTail的nextl2如果l2遍历结束newTail的nextl1
代码
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode l1 list1;ListNode l2 list2;if(l1null) {return l2;}if(l2null) {return l1;}ListNode newHead null;ListNode newTail null;while (l1 ! null l2 ! null) {if (l1.val l2.val) {//if (newTail null) {newHead newTail l1;l1 l1.next;} else {newTail.next l1;newTail l1;l1 l1.next;}} else {if (newTail null) {newHead newTail l2;l2 l2.next;} else {newTail.next l2;newTail l2;l2 l2.next;} }}//if(l1null) {newTail.next l2;}else {newTail.next l1;}return newHead;}
}6. 分割链表 题目链接链表分割 题目要求 如图小于x的结点在前大于等于x的结点在后不改变原来的顺序意思是5在4之前操作之后5还在4之前 解题思路 定义LeftHead左边部分的头结点和LeftTail左边部分的尾结点维护左边部分小于x的结点定义RightHead右边部分的头结点和RightTail右边部分的尾结点维护右边部分大于等于x的结点将小于x的结点尾插到左边部分将大于等于x的结点尾插到右边部分接着将左右两边连接即可 注意事项 可能会出现链表中所有的结点都小于x或者都大于等于x如果都小于x直接返回左边部分如果都大于等于x直接返回右边部分 代码
public ListNode partition(ListNode pHead, int x) {// write code hereif (pHead null) {return null;}ListNode cur pHead;ListNode LeftHead null;//左边部分的头ListNode LeftTail null;//左边部分的尾ListNode RightHead null;//右边部分的头ListNode RightTail null;//右边部分的尾while (cur ! null) {if (cur.val x) {if (LeftHead null) {//第一次插LeftHead LeftTail cur;} else {LeftTail.next cur;LeftTail LeftTail.next;}cur cur.next;} else {if (RightHead null) {//第一次插RightHead RightTail cur;} else {RightTail.next cur;RightTail RightTail.next;}cur cur.next;}}if (LeftHead null) {return RightHead;}LeftTail.next RightHead;if (RightHead ! null) {RightTail.next null;}return LeftHead;}7. 回文链表 题目链接回文链表 题目要求 判断链表是否为回文链表回文指的是从前往后看和从后往前看是一样的如1234321是回文121是回文12不是回文 解题思路 找到中间结点然后将后半部分反转接着定义两个临时结点一个指向头另一个指向后半部分依次两两比较判断结点的val值是否相等。首先找到中间结点前面我们实现过了反转结点我们也实现过了所以这个题一下就变简单了 代码
class Solution {public boolean isPalindrome(ListNode head) {if (head null) {return false;}ListNode fast head;ListNode slow head;//while (fast ! nullfast.next!null) {fast fast.next.next;slow slow.next;}ListNode Newhead reverseList(slow);ListNode tmp1 head;ListNode tmp2 Newhead;while(tmp2!null) {//if(tmp2.val!tmp1.val) {return false;} else {tmp1 tmp1.next;tmp2 tmp2.next;}}return true;}//翻转链表public ListNode reverseList(ListNode head) {if (head null) {return head;}ListNode cur head.next;head.next null;while (cur ! null) {ListNode curNext cur.next;cur.next head;head cur;cur curNext;}return head;}
}8. 找相交链表的公共结点 题目链接相交链表 题目要求 返回两个链表相交的结点如果不相交返回null 解题思路 分别计算两个链表的长度定义两个临时结点分别指向两个链表的头让长度长的链表临时结点往后走长度的差值步接着两个临时结点一起走
代码
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if(headAnull||headBnull) {return null;}int countA 0;//记录A的长度int countB 0;//记录B的长度ListNode curA headA;ListNode curB headB;while(curA!null) {countA;curA curA.next;}while(curB!null) {countB;curB curB.next;}if(countAcountB) {//A链表更长for(int i0;icountA-countB;i) {headA headA.next;}}if(countAcountB) {//B链表更长for(int i0;icountB-countA;i) {headB headB.next;}}//让临时结点回去curA headA;curB headB;//一起走while(curA!null) {if(curAcurB) {return curA;}curA curA.next;curB curB.next;}return curB;}
}9. 判断链表是否有环 题目链接环形链表 题目要求 判断链表是否存在环如果存在环返回true否则返回false 解题思路 还是快慢指针想象一下你和你对象在你的宿舍楼下你们一起往操场跑环形操场你们两个的速度肯定有快有慢不可能完全一样你们跑呀跑肯定会在操场中相遇。链表也是如此这里我们让fast的速度为slow的两倍fast每次走两步slow每次走一步 代码
public class Solution {public boolean hasCycle(ListNode head) {if(head null) {return false;}ListNode fast head;ListNode slow head;while (fast ! null fast.next!null) {fast fast.next.next;slow slow.next;if(fast slow) {return true;}}return false;}
}10. 返回链表环的入口 题目链接环形链表Ⅱ 题目要求 如果链表存在环返回环的入口如果不存在环返回null 解题思路 如图
代码
public class Solution {public ListNode detectCycle(ListNode head) {if (head null) {return null;}ListNode fast head;ListNode slow head;while (fast ! null fast.next ! null) {fast fast.next.next;slow slow.next;if (fast slow) {// 两人相遇,说明链表成环while (head ! slow) {slow slow.next;head head.next;}return head;}}return null;}
}今天的内容就到这里感谢老铁们的点赞、收藏、评论~❤
