LeetCode题：83删除排序链表中的重复元素 141环形链表

超、凢脫俗 2024-02-19 08:19 18阅读 0赞

## 83删除排序链表中的重复元素 ##

### 题目内容 ###

给定一个已排序的链表的头 `head` ， *删除所有重复的元素，使每个元素只出现一次* 。返回 *已排序的链表* 。

**示例 1：**

![775123643a32b4aadef636eb439bd5a6.jpeg][]

输入：head = [1,1,2]
    输出：[1,2]

**示例 2：**

![b2132cd8b067d8299d084da498470a97.jpeg][]

输入：head = [1,1,2,3,3]
    输出：[1,2,3]

### 思路： ###

> 非递归法：这题很简单，只需遍历一遍有序链表，判断当前节点和下一个节点是否相同，如果相同，就跳过下一个节点，到下下一个节点，如图：时间复杂度：O(N)
> 
> ![a800af2604c144669ceb3bd67ca17f46.png][]

> 递归法：如图
> 
> ![8f394c3d349245b9ba3380628df2e92a.png][]
> 
> 我们从图可以看到，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：**

![66f50941a5dcf4cd2e2ea0ce209ca3ba.png][]

输入：head = [3,2,0,-4], pos = 1
    输出：true
    解释：链表中有一个环，其尾部连接到第二个节点。

**示例 2：**

![4291c37974294ebfcbe7c96688011b85.png][]

输入：head = [1,2], pos = 0
    输出：true
    解释：链表中有一个环，其尾部连接到第一个节点。

**示例 3：**

![1a7f0b7a586954fc46faa2227d3e0416.png][]

输入：head = [1], pos = -1
    输出：false
    解释：链表中没有环。

### 思路： ###

这道题其实是一个追逐问题，想象有一个环形跑道，有一个男生和一个女生，男生跑步的速度是女生的2倍，那么在这个环形跑道中，两人在同一起点同时跑，那么男生是不是会比女生多跑一圈，在第一次遇见女生后，第二次遇见女生是女生刚好跑完一圈，男生刚好跑完2两圈，如果不同时跑呢？那女生是不是也迟早会被追上？

![c7c8c6804bd34cc5b9ac0d15e83474f3.png][]

那么这个环形链表也一样，我们可以定义一个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;
        }
    }

##  ##

[775123643a32b4aadef636eb439bd5a6.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/19/91ce4f00c53e4a0eb333383447165f9b.png
[b2132cd8b067d8299d084da498470a97.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/19/19dc94cd25b54055bdd37c08df4faeeb.png
[a800af2604c144669ceb3bd67ca17f46.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/19/87f02558080d4a659828dbde07301d82.png
[8f394c3d349245b9ba3380628df2e92a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/19/f80d88e25b814fb4afe35e58f72ee0cf.png
[66f50941a5dcf4cd2e2ea0ce209ca3ba.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/19/99f607d4525f4a199bed14f0d0355350.png
[4291c37974294ebfcbe7c96688011b85.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/19/ee45f9c54c6241159e1f175e37dc6989.png
[1a7f0b7a586954fc46faa2227d3e0416.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/19/7bef06c86aec40dda1c39e061a2bf30f.png
[c7c8c6804bd34cc5b9ac0d15e83474f3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/19/6e6b65ff168c40d49c4719d8c5c0d789.png