【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;}