快慢指针找中间节点
如果是偶数节点靠前的，fast = head.fast
是靠后的，fast = head
标准用法是fast = head 靠后这个，注意最开始 它俩是相等的
这两个奇数节点数的话都是中间的。
def middle(self, head):
# 找中间节点
'''
如果是偶数节点靠前的，fast = head.fast
是靠后的，fast = head
'''
newhead = ListNode(0)
newhead.next = head
pre = newhead
slow, fast = head, head.next
while fast and fast.next:
fast = fast.next.next
pre = slow
slow = slow.next
print(pre.val, slow.val)
return slow
复杂链表的复制
- 迭代+拆分: 可以每个节点都在后面有个一样的，然后设置random成员, 再拆分下拉
- 回溯+hash: 可以递归的复制，记得缓存下对应的复制值，没有的话就生成一个，有的话直接引用。
class Solution {
public:
unordered_map<Node*, Node*> cachedNode;
Node* copyRandomList(Node* head) {
if (head == nullptr) {
return nullptr;
}
if (!cachedNode.count(head)) {
Node* headNew = new Node(head->val);
cachedNode[head] = headNew;
headNew->next = copyRandomList(head->next);
headNew->random = copyRandomList(head->random);
}
return cachedNode[head];
}
};
链表反转
def reverse1(self, head):
# 递归
if not head or not head.next: return head
last = self.reverse1(head.next)
head.next.next = head
head.next = None
return last
def reverse2(self, head):
# 改变当前next值，pre->head->nxt, 改head的
pre = None
while head:
nxt = head.next
head.next = pre
pre = head
head = nxt
return pre
def reverse3(self, head):
# 头插法反转
newhead = ListNode(0)
while head:
nxt = head.next
x = newhead.next
head.next = x
newhead.next = head
head = nxt
return newhead.nex
链表重构
参考：https://leetcode-cn.com/problems/reorder-list/
给定一个单链表 L 的头节点 head ，单链表 L 表示为：
L0 → L1 → … → Ln - 1 → Ln 请将其重新排列后变为：
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
判断是否有环和找环的入口
一种方法是hash表，这里不多说。下面展示快慢指针做法
注意这里fast = head. 这是标准用法.
检查是否有环:
class Solution:
def hasCycle(self, head: ListNode) -> bool:
slow, fast = head, head
while fast:
slow = slow.next
if not fast.next: return False
fast = fast.next.next
if fast == slow:
return True
return False
找环的入口：
# 找环入口
# 先找到slow和fast相遇点，然后fast从head开始，一样速度遍历
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
fast, slow = head, head
while fast:
slow = slow.next
if not fast.next:
return None
fast = fast.next.next
if fast == slow:
fast = head
while fast != slow:
slow = slow.next
fast = fast.next
return fast
return None
两个链表的第一个公共节点
一种方法是hash表。
设 A 的长度为 a + c，B 的长度为 b + c，其中 c 为尾部公共部分长度，可知 a + c + b = b + c + a。
当访问 A 链表的指针访问到链表尾部时，令它从链表 B 的头部重新开始访问链表 B；同样地，当访问 B 链表的指针访问到链表尾部时，令它从链表 A 的头部重新开始访问链表 A。这样就能控制访问 A 和 B 两个链表的指针能同时访问到交点。
找出2个链表的长度，然后让长的先走两个链表的长度差，然后再一起走 （因为2个链表用公共的尾部）
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
ListNode pA = headA, pB = headB;
while (pA != pB) {
pA = pA == null ? headB : pA.next;
pB = pB == null ? headA : pB.next;
}
return pA;
}
}
链表排序
归并排序 自上而下
class Solution:
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return head
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
a, slow.next, b = head, None, slow.next
a, b = self.sortList(a), self.sortList(b)
h = t = ListNode(0)
while a and b:
if a.val < b.val:
t.next, a = a, a.next
else:
t.next, b = b, b.next
t = t.next
t.next = a if a else b
return h.next
归并排序 自下而上
对于非递归的归并排序，需要使用迭代的方式替换cut环节： 我们知道，cut环节本质上是通过二分法得到链表最小节点单元，再通过多轮合并得到排序结果。 每一轮合并merge操作针对的单元都有固定长度intv，例如： 第一轮合并时intv = 1，即将整个链表切分为多个长度为1的单元，并按顺序两两排序合并，合并完成的已排序单元长度为2。 第二轮合并时intv = 2，即将整个链表切分为多个长度为2的单元，并按顺序两两排序合并，合并完成已排序单元长度为4。 以此类推，直到单元长度intv >= 链表长度，代表已经排序完成。 根据以上推论，我们可以仅根据intv计算每个单元边界，并完成链表的每轮排序合并，例如: 当intv = 1时，将链表第1和第2节点排序合并，第3和第4节点排序合并，……。 当intv = 2时，将链表第1-2和第3-4节点排序合并，第5-6和第7-8节点排序合并，……。 当intv = 4时，将链表第1-4和第5-8节点排序合并，第9-12和第13-16节点排序合并，……。 此方法时间复杂度O(nlogn)O(nlogn)，空间复杂度O(1)O(1)。
class Solution:
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
h, length, intv = head, 0, 1
while h: h, length = h.next, length + 1
res = ListNode(0)
res.next = head
while intv < length:
pre, h = res, res.next
while h:
h1, i = h, intv
while h and i: h, i = h.next, i - 1
if i: break
h2, i = h, intv
while h and i: h, i = h.next, i - 1
c1, c2 = intv, intv - i
while c1 and c2:
if h1.val < h2.val:
pre.next, h1, c1 = h1, h1.next, c1 - 1
else:
pre.next, h2, c2 = h2, h2.next, c2 - 1
pre = pre.next
pre.next = h1 if c1 else h2
while c1 > 0 or c2 > 0:
pre, c1, c2 = pre.next, c1 - 1, c2 - 1
pre.next = h
intv *= 2
return res.next
快速排序
partion时可以维护左右链，然后再结合起来。就是左边<，右边>=的情况了。
双向链表模板
class DNode:
def __init__(self, val):
self.val = val
self.pre = None
self.next = None
def __repr__(self):
return f"{self.val}:{self.next}"
class DoubleLinkedList:
'''
remove the node, and return the pre node
'''
def remove(sefl, node):
pre = node.pre
next = node.next
if pre:
pre.next = next
if next:
next.pre = pre
return pre
'''
add node the to the right, and return the node
'''
def add_new_node_to_right(self, pre, node):
if not pre:
return node
pnext = pre.next
pre.next = node
node.pre = pre
node.next = pnext
if pnext:
pnext.pre = node
return node
d = DoubleLinkedList()