建站快车,网站怎么做分站,建网站怎么起名字,php做的网站模板下载地址83删除排序链表中的重复元素
题目内容
给定一个已排序的链表的头 head #xff0c; 删除所有重复的元素#xff0c;使每个元素只出现一次 。返回 已排序的链表 。 示例 1#xff1a; 输入#xff1a;head [1,1,2]
输出#xff1a;[1,2]示例 2#xff1a; 输入#xf…83删除排序链表中的重复元素
题目内容
给定一个已排序的链表的头 head 删除所有重复的元素使每个元素只出现一次 。返回 已排序的链表 。 示例 1 输入head [1,1,2]
输出[1,2]示例 2 输入head [1,1,2,3,3]
输出[1,2,3]思路 非递归法这题很简单只需遍历一遍有序链表判断当前节点和下一个节点是否相同如果相同就跳过下一个节点到下下一个节点如图时间复杂度O(N) 递归法如图 我们从图可以看到1和1相等那么我们头结点的next指向就是2了那么这就出现了一个新的链表我们就要删除这新的节点链表中的重复元素依次类推这不就是递归吗 时间复杂度O(N) 空间复杂度要比非递归的多 代码展示
非递归法
class Solution {public ListNode deleteDuplicates(ListNode head) {if(head null) {return head;}ListNode listNode head;while(listNode.next ! null) {if(listNode.val listNode.next.val) {listNode.next listNode.next.next;} else {listNode listNode.next;}}return head;}
}
递归法
class Solution {
public ListNode deleteDuplicates(ListNode head) {if(head null || head.next null) {return head;}head.next deleteDuplicates(head.next);return head.val head.next.val ? head.next : head;}
} 141环形链表
题目内容
给你一个链表的头节点 head 判断链表中是否有环。
如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。注意pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 则返回 true 。 否则返回 false 。 示例 1 输入head [3,2,0,-4], pos 1
输出true
解释链表中有一个环其尾部连接到第二个节点。示例 2 输入head [1,2], pos 0
输出true
解释链表中有一个环其尾部连接到第一个节点。示例 3 输入head [1], pos -1
输出false
解释链表中没有环。
思路
这道题其实是一个追逐问题想象有一个环形跑道有一个男生和一个女生男生跑步的速度是女生的2倍那么在这个环形跑道中两人在同一起点同时跑那么男生是不是会比女生多跑一圈在第一次遇见女生后第二次遇见女生是女生刚好跑完一圈男生刚好跑完2两圈如果不同时跑呢那女生是不是也迟早会被追上 那么这个环形链表也一样我们可以定义一个slow和fast链表slow一次走一步fast一次走两步只要fast或者是fast.next不为null就一直遍历这个链表如果slow和fast相遇了那么这个链表肯定是环形链表如果没在遍历了即fast为null或者是fast.next为空那么这一定不是环形链表
代码展示
public class Solution {public boolean hasCycle(ListNode head) {if(head null) {return false;}ListNode slow head;ListNode fast head;while(fast.next ! null fast.next.next ! null) {slow slow.next;fast fast.next.next;if(slow fast) {return true;}}return false;}
}
