【算法题解】 Day18 链表
剑指 Offer 24. 反转链表
题目
剑指 Offer 24. 反转链表 难度：easy
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL限制：
0 <= 节点个数 <= 5000
方法一：迭代
思路
假设链表为 1 → 2 → 3 → ∅，我们想要把它改成 ∅ ← 1 ← 2 ← 3。
在遍历链表时，将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。
解题
Python：
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
cur, pre = head, None
while cur:
tmp = cur.next # 暂存后继节点 cur.next
cur.next = pre # 修改 next 引用指向
pre = cur # pre 暂存 cur
cur = tmp # cur 访问下一节点
return preJava：
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}方法二：递归
思路
递归版本稍微复杂一些，其关键在于反向工作。假设链表的其余部分已经被反转，现在应该如何反转它前面的部分？
假设链表为：
若从节点 nk+1 到 nm 已经被反转，而我们正处于 nk
我们希望 nk+1的下一个节点指向 nk，所以，nk.next.next=nk
需要注意的是 n1的下一个节点必须指向 ∅。如果忽略了这一点，链表中可能会产生环。
解题
Python：
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
def recur(cur, pre):
if not cur: return pre # 终止条件
res = recur(cur.next, cur) # 递归后继节点
cur.next = pre # 修改节点引用指向
return res # 返回反转链表的头节点
return recur(head, None) # 调用递归并返回Java：
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
}剑指 Offer 35. 复杂链表的复制
题目
剑指 Offer 35. 复杂链表的复制 难度：medium
请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
示例 1：
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]示例 2：
输入： head = [[1,1],[2,1]]
输出： [[1,1],[2,1]]示例 3：
输入： head = [[3,null],[3,0],[3,null]]
输出： [[3,null],[3,0],[3,null]]示例 4：
输入： head = []
输出： []
解释： 给定的链表为空（空指针），因此返回 null。提示：
-10000 <= Node.val <= 10000Node.random为空（null）或指向链表中的节点。- 节点数目不超过 1000 。
方法一：回溯 + 哈希表
思路
本题要求我们对一个特殊的链表进行深拷贝。如果是普通链表，我们可以直接按照遍历的顺序创建链表节点。而本题中因为随机指针的存在，当我们拷贝节点时，「当前节点的随机指针指向的节点」可能还没创建，因此我们需要变换思路。一个可行方案是，我们利用回溯的方式，让每个节点的拷贝操作相互独立。对于当前节点，我们首先要进行拷贝，然后我们进行「当前节点的后继节点」和「当前节点的随机指针指向的节点」拷贝，拷贝完成后将创建的新节点的指针返回，即可完成当前节点的两指针的赋值。
具体地，我们用哈希表记录每一个节点对应新节点的创建情况。遍历该链表的过程中，我们检查「当前节点的后继节点」和「当前节点的随机指针指向的节点」的创建情况。如果这两个节点中的任何一个节点的新节点没有被创建，我们都立刻递归地进行创建。当我们拷贝完成，回溯到当前层时，我们即可完成当前节点的指针赋值。注意一个节点可能被多个其他节点指向，因此我们可能递归地多次尝试拷贝某个节点，为了防止重复拷贝，我们需要首先检查当前节点是否被拷贝过，如果已经拷贝过，我们可以直接从哈希表中取出拷贝后的节点的指针并返回即可。
在实际代码中，我们需要特别判断给定节点为空节点的情况。
解题
Python：
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
if not head: return
dic = {}
# 复制各节点，并建立 "原节点 -> 新节点" 的 Map 映射
cur = head
while cur:
dic[cur] = Node(cur.val)
cur = cur.next
cur = head
# 构建新节点的 next 和 random 指向
while cur:
dic[cur].next = dic.get(cur.next)
dic[cur].random = dic.get(cur.random)
cur = cur.next
# 返回新链表的头节点
return dic[head]Java：
class Solution {
Map<Node, Node> cachedNode = new HashMap<Node, Node>();
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
if (!cachedNode.containsKey(head)) {
Node headNew = new Node(head.val);
cachedNode.put(head, headNew);
headNew.next = copyRandomList(head.next);
headNew.random = copyRandomList(head.random);
}
return cachedNode.get(head);
}
}