[数据结构与算法]【算法题解】 Day4 链表

? 算法题解系列文章旨在精选重点与易错的算法题，总结常见的算法思路与可能出现的错误，以实战习题的形式理解算法，使用算法。

🔥 本文已收录于算法刷题系列专栏： 算法题解 欢迎订阅，持续更新。

🎉 欢迎关注👀 点赞👍 收藏? 留言📝

💬 代码成就万世基，积沙镇海；梦想永在凌云意，意气风发； 𝓼𝓲𝓭𝓲𝓸𝓽

?

876. 链表的中间结点

题目

876. 链表的中间结点 难度：easy

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

示例 2：

输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

提示：

• 给定链表的结点数介于 1 和 100 之间。

?

方法一：数组

思路

关于链表定位的题目，如果不限制额外空间的话，可以优先考虑开辟数组来存储；

这里将链表的所有节点拷贝到数组上，然后数组长度取半即可；

ListNode -> Array
return Array[len(Array)/2]

?

解题

Python：

class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        A = [head]
        while A[-1].next:
            A.append(A[-1].next)
        return A[len(A) // 2]

Java：

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode[] A = new ListNode[100];
        int t = 0;
        while (head != null) {
            A[t++] = head;
            head = head.next;
        }
        return A[t / 2];
    }
}

?

方法二：单一指针

思路

上述方法一虽然简单，但是需要开辟额外的空间，那么我们应该如何做优化呢？

基于方法一的原理，我们可以使用单一指针的方法来解决，首先，先遍历一次链表，来获取链表长度，其次，再遍历一遍，来获取链表的中间节点；

while ..:
    # 遍历节点，获取链表长度
    len += 1

cnt = 0 # 表示当前指针位置
while cnt < len/2:
    node = node.next

return node

?

解题

Python：

class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        n, cur = 0, head
        while cur:
            n += 1
            cur = cur.next
        k, cur = 0, head
        while k < n // 2:
            k += 1
            cur = cur.next
        return cur

Java：

class Solution {
    public ListNode middleNode(ListNode head) {
        int n = 0;
        ListNode cur = head;
        while (cur != null) {
            ++n;
            cur = cur.next;
        }
        int k = 0;
        cur = head;
        while (k < n / 2) {
            ++k;
            cur = cur.next;
        }
        return cur;
    }
}

?

方法三：快慢指针

思路

方法二虽然不需要额外开辟空间，但需要遍历两次，那我们可以继续优化，使其变成一次吗？

用两个指针 slow 与 fast 一起遍历链表。slow 一次走一步，fast 一次走两步。那么当 fast 到达链表的末尾时，slow 必然位于中间。

?

解题

Python：

class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

Java：

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

?

142. 环形链表 II

题目

142. 环形链表 II 难度：medium

给定一个链表的头节点 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
解释： 链表中没有环。

提示：

• 链表中节点的数目范围在范围 [0, 104] 内
• -105 <= Node.val <= 105
• pos 的值为 -1 或者链表中的一个有效索引

?

方法一：哈希表

思路

首先就是想到使用哈希表进行存储，如果遇到重复的就说明是有环了；

?

解题

Python：

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        dict, i, j = {}, 0, 0
        while head:
            if head not in dict:
                dict[head] = i
                i += 1
            else:
                while j < dict[head]:
                    head = head.next
                    j += 1
                return head
            head = head.next
        return None

Java：

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode pos = head;
        Set<ListNode> visited = new HashSet<ListNode>();
        while (pos != null) {
            if (visited.contains(pos)) {
                return pos;
            } else {
                visited.add(pos);
            }
            pos = pos.next;
        }
        return null;
    }
}

?

方法二：快慢指针

思路

我们使用两个指针，fast 与 slow。它们起始都位于链表的头部。随后，slow 指针每次向后移动一个位置，而 fast 指针向后移动两个位置。如果链表中存在环，则fast 指针最终将再次与 slow 指针在环中相遇。

?

解题

Python：

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        fast = slow = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                ans = head
                while ans != slow:
                    slow = slow.next
                    ans = ans.next
                return ans
        return

Java：

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode slow = head, fast = head;
        while (fast != null) {
            slow = slow.next;
            if (fast.next != null) {
                fast = fast.next.next;
            } else {
                return null;
            }
            if (fast == slow) {
                ListNode ptr = head;
                while (ptr != slow) {
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }
        return null;
    }
}

?

后记

以上就是 【算法题解】 Day4 链表 的所有内容了，创作不易，多多支持 👍👍👍

我是 𝓼𝓲𝓭𝓲𝓸𝓽，期待你的关注 💖💖💖

🔥 系列专栏： 算法题解