这是极客争哥专栏链表题目 (春节加加练)
Linked List Cycle I（环形链表）
- https://leetcode-cn.com/problems/linked-list-cycle/
合并 k 个排序链表
- https://leetcode-cn.com/problems/merge-k-sorted-lists/
补充一个 LeetCode206 - 反转链表（面试常见题目）
- https://leetcode-cn.com/problems/reverse-linked-list/
共 3 题，开搞（要求 py Java）
Leetcode141
给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。
你能用 O(1)（即，常量）内存解决此问题吗？
遍历整个数组, 给出的数据包含在集合中则说明有环, 返回 True; 若遍历完毕, 则说明无环, 返回 False
py set 暴力解法
代码语言：javascript复制class Solution:
def hasCycle(self, head: ListNode) -> bool:
"""
暴力法：通过遍历链表，用set来存储访问的节点，如果在set出现一样的节点，说明有坏，时间复杂度O(n)
:type head: ListNode
"""
p = head
st = set()
while p:
if p in st:
return True
st.add(p)
p = p.next
print(st)
return Falsejava hashset 暴力解法
代码语言：javascript复制import java.util.HashSet;
public class Solution {
public boolean hasCycle(ListNode head) {
Set<ListNode> nodeSeen = new HashSet<>();
while(head !=null){
if (nodeSeen.contains(head)){
return true;
}else {
nodeSeen.add(head);
}
head = head.next;
}
return false;
}
}时间空间复杂度都是 O(n)
题目要求用 $O(1)$ 空间复杂度
这道题考的是快慢指针 $O(1)$ 空间复杂度
通过使用具有 不同速度 的快、慢两个指针遍历链表，空间复杂度可以被降低至 $O(1)$。慢指针每次移动一步，而快指针每次移动两步。
如果列表中不存在环，最终快指针将会最先到达尾部，此时我们可以返回 false。
进阶的要求是以 O(1) 的空间复杂度实现, 想象这样一个场景, 你和一个朋友一起散步, 你每次移动两步, 朋友每次一步, 如为单向定长道路, 你必然先到达重点. 若是环绕操场, 则你们终将相遇.
py 快慢指针
代码语言：javascript复制class Solution(object):
def hasCycle(self, head):
slow = fast = head
while slow and fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return FalseJava 快慢指针
代码语言：javascript复制public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while (slow != fast) {
if (fast == null || fast.next == null) {
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}双指针的应用比较广，除了判断链表是否有环，也可以用于删除数组重复元素问题、求和问题等
Leetcode23
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
代码语言：javascript复制输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6暴力遍历
遍历所有链表，将所有节点的值放到一个数组中。 将这个数组排序，然后遍历所有元素得到正确顺序的值。 用遍历得到的值，创建一个新的有序链表。
时间复杂度：$O(Nlog N)$ ，其中 N 是节点的总数目
空间复杂度：$O(N)$。
排序花费 $O(N)$ 空间（这取决于你选择的算法）。 创建一个新的链表花费 $O(N)$ 的空间。
代码语言：javascript复制class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode :
"""
:type lists: List[ListNode]
"""
self.nodes = []
head = point = ListNode(0)
for l in lists:
while l:
self.nodes.append(l.val)
l = l.next
for x in sorted(self.nodes):
point.next = ListNode(x)
point = point.next
return head.next但是这题考得是 $ 优先队列 (priority queue)$ 知识点
普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。
优先队列具有最高级先出 （first in, largest out）的行为特征。通常采用堆数据结构来实现。
假设你是一名体育老师，有 33 个班的学生，他们已经按照身高从矮到高排好成了 33 列纵队，现在要把这 33 个班的学生也按照身高从矮到高排列 11 列纵队。我们可以这么做：
1、让 33 个班的学生按列站在你的面前，这时你能看到站在队首的学生的全身； 2、每一次队首的 33 名同学，请最矮的同学出列到 “队伍 4”（即我们最终认为排好序的队列），出列的这一列的后面的所有同学都向前走一步（其实走不走都行，只要你能比较出站在你面前的 3 位在队首的同学同学的高矮即可）； 3、重复第 2 步，直到 33 个班的同学全部出列完毕。
作者：liweiwei1419 链接：https://leetcode-cn.com/problems/merge-k-sorted-lists/solution/tan-xin-suan-fa-you-xian-dui-lie-fen-zhi-fa-python/
代码语言：javascript复制import heapq
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
l = []
size = len(lists)
for index in range(size):
# 针对一些特殊的测试用例，有的链表可能是空链表
if lists[index]:
heapq.heappush(l, (lists[index].val, index))
dummy_node = ListNode(-1)
cur = dummy_node
while l:
_, index = heapq.heappop(l)
# 定位到此时应该出列的那个链表的头结点
head = lists[index]
# 开始“穿针引线”
cur.next = head
cur = cur.next
# 同样不要忘记判断到链表末尾结点的时候
if head.next:
# 刚刚出列的那个链表的下一个结点成为新的链表头结点加入优先队列
heapq.heappush(l, (head.next.val, index))
# 切断刚刚出列的那个链表的头结点引用
lists[index] = head.next
head.next = None
return dummy_node.nextJava 优先队列 (priority queue)
代码语言：javascript复制public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> queue = new PriorityQueue<>(Comparator.comparingInt(node -> node.val));
ListNode dummy = new ListNode(0);
ListNode p = dummy;
queue.addAll(Stream.of(lists).filter(Objects::nonNull).collect(Collectors.toList()));
while (!queue.isEmpty()) {
ListNode node = queue.poll();
p.next = node;
p = p.next;
if (node.next != null)
queue.add(node.next);
}
return dummy.next;
}LeetCode206
反转一个单链表。
示例:
代码语言：javascript复制输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL假设存在链表 1 → 2 → 3 → Ø，我们想要把它改成 Ø ← 1 ← 2 ← 3。
在遍历列表时，将当前节点的 next 指针改为指向前一个元素。由于节点没有引用其上一个节点，因此必须事先存储其前一个元素。在更改引用之前，还需要另一个指针来存储下一个节点。不要忘记在最后返回新的头引用！
复杂度分析
时间复杂度：O(n)，假设 n 是列表的长度，时间复杂度是 O(n)。 空间复杂度：O(1)。
Java
代码语言：javascript复制class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
}py
代码语言：javascript复制class Solution:
def reverseList(self, head: ListNode) -> ListNode:
"""
:type head: ListNode
"""
cur, prev = head, None
while cur:
cur.next, prev, cur = prev, cur, cur.next
return prev
