【算法题解】 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 curJava：
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 slowJava：
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 <= 105pos的值为-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 NoneJava：
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
returnJava：
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;
}
}腾讯云开发者
