【leetcode】链表（2）
目录
1. 环形链表
解题思路
2. 环形链表 II
解题思路
3. 删除排序链表中的重复元素
解题思路
4. 删除排序链表中的重复元素 II
解题思路
5. 移除链表元素
解题思路
6. 链表的中间结点
解题思路
1. 环形链表
OJ：环形链表
给你一个链表的头节点
head，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪
next指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数pos来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos不作为参数进行传递 。仅仅是为了标识链表的实际情况。如果链表中存在环 ，则返回
true。 否则，返回false。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
解题思路
快慢指针
快指针走两步，慢指针走一步，如果链表带环，两个最终肯定会在环内相遇；如果链表不带环，快指针肯定会走到链表的末尾
public boolean hasCycle(ListNode head) {if(head == null || head.next == null){return false;}ListNode low = head;ListNode fast = head;while(fast != null && fast.next != null){fast = fast.next.next;low = low.next;if(fast == low){return true;}}return false;}2. 环形链表 II
OJ：环形链表 II
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪
next指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数pos来表示链表尾连接到链表中的位置（索引从 0 开始）。如果pos是-1，则在该链表中没有环。注意：pos不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改 链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
解题思路
public ListNode detectCycle(ListNode head) {
// 快慢指针相遇时，引入新节点从链表头开始，慢的一定会和新节点在环形第一个节点相遇ListNode low = head;ListNode fast = head;while (fast != null && fast.next != null){low = low.next;fast = fast.next.next;if(fast == low){ListNode third = head;while (third != low){third = third.next;low = low.next;}return low;}}return null;}3. 删除排序链表中的重复元素
OJ：删除排序链表中的重复元素
给定一个已排序的链表的头
head， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
示例 1：
输入：head = [1,1,2] 输出：[1,2]
示例 2：
输入：head = [1,1,2,3,3] 输出：[1,2,3]
解题思路
- 思路1
由于给定的链表是排好序的，因此重复的元素在链表中出现的位置是连续的，因此我们只需要对链表进行一次遍历，就可以删除重复的元素。当cur与cur.next的元素相等时，删除cur.next。下面给出了两种实现方法。
public ListNode deleteDuplicates(ListNode head) { if(head == null || head.next == null){return head;}
// 至少有两个节点
// 头节点val在范围之外if (head == null) {return head;}ListNode cur = head;while (cur.next != null) {if (cur.val == cur.next.val) {cur.next = cur.next.next;} else {cur = cur.next;}}return head;}public ListNode deleteDuplicates(ListNode head) {if(head ==null ||head.next == null){return null;}head = deleteDuplicates(head.next);return head.val == head.next.val ? head.next : head;}4. 删除排序链表中的重复元素 II
OJ：删除排序链表中的重复元素 II
给定一个已排序的链表的头
head， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
示例 1：
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]
示例 2：
输入：head = [1,1,1,2,3]
输出：[2,3]
解题思路
public ListNode deleteDuplicates(ListNode head) {// 1.base caseif (head == null || head.next == null) {return head;}ListNode dummyHead = new ListNode(-101);dummyHead.next = head;ListNode prev = dummyHead;ListNode cur = prev.next;while (cur != null) {ListNode sec = cur.next;if (sec == null) {break;}if (cur.val != sec.val) {prev = prev.next;}else {// 此时cur和sec相等while (sec != null && cur.val == sec.val) {sec = sec.next;}// 此时sec一定走到第一个和cur不相等的结点// prev .. sec全都是待删除的结点prev.next = sec;}cur = sec;}return dummyHead.next;} //递归法// 传入一个以head为头节点的链表，就能删除其中所有的重复元素，重复元素一个都不保留public ListNode deleteDuplicates(ListNode head) {// 1.base caseif(head == null || head.next == null) {return head;}if(head.val != head.next.val) {head.next = deleteDuplicates(head.next);return head;}else {// 头节点就是重复的节点，先处理完头节点的情况ListNode newHead = head.next;while(newHead != null && newHead.val == head.val) {newHead = newHead.next;}// 此时newHead一定不是待删除的结点，最终整个传入函数，返回更新后的值即可return deleteDuplicates(newHead);}}5. 移除链表元素
OJ：移除链表元素
给你一个链表的头节点
head和一个整数val，请你删除链表中所有满足Node.val == val的节点，并返回 新的头节点 。
示例 1：
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
示例 2：
输入：head = [], val = 1
输出：[]
示例 3：
输入：head = [7,7,7,7], val = 7
输出：[]
解题思路
（1）先判断头节点元素是否与val相等，相等删除头节点（head = head.next）
（2）判断后面的节点元素是否与val相等，相等删除（prev.next = prev.next.next;）；不相等往下继续遍历。直至到链表尾部。
public ListNode removeElements(ListNode head, int val) {while (head != null && head.val == val) {head = head.next;}// 有头节点的链表解法ListNode dummyHead = new ListNode();//与原链表建立联系dummyHead.next = head;ListNode prev = dummyHead;while(prev.next != null){if(prev.next.val == val){prev.next = prev.next.next;}else{prev = prev.next;}}return dummyHead.next;}public ListNode removeElements(ListNode head, int vals) {if(head == null){return null;}head.next = removeElements(head.next,vals);return head.val == vals ? head.next :head;}6. 链表的中间结点
给你单链表的头结点
head，请你找出并返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
示例 1：
输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间结点，值为 3 。
示例 2：
输入：head = [1,2,3,4,5,6]
输出：[4,5,6]
解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。
解题思路
- 思路1
快慢指针，慢指针走一步，快指针走两步，当快指针走到链表最后一个或走到空时，慢指针走到中间节点。
public ListNode middleNode(ListNode head) {ListNode fast = head;ListNode low = head;while (fast!= null && fast.next != null){low = low.next;fast = fast.next.next;}return low;}- 思路2
先求出链表长度，再除以2，就是中间节点的位置了，从链表头遍历到该位置再返回。
public ListNode middleNode(ListNode head) {int length = 0;ListNode node = head;while(node != null){length++;node = node.next;}length = length / 2;node = head;for(int i =0;i<length;i++){node = node.next;}return node;}