剑指Offer 06. 从尾到头打印链表
可借助栈。
或先遍历列表得到元素数，开辟数组空间倒序填入。
剑指 Offer 24. 反转链表
可借助栈：
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null) return null;
Deque<ListNode> d = new LinkedList<>();
ListNode cur = head;
while(cur != null) {
d.addLast(cur);
cur = cur.next;
}
ListNode nhead = d.pollLast();
cur = nhead;
while(!d.isEmpty()) {
cur.next = d.pollLast();
cur = cur.next;
}
cur.next = null;
return nhead;
}
}
双指针：
双指针所定位的两个结点的指向关系要反过来，这会导致后方指针原本所指的结点丢失。因此每次双指针的移动要借助第三个指针解决结点丢失问题，使得双指针能够进行位置更新。
class Solution {
public ListNode reverseList(ListNode head) {
ListNode p1 = null, p2 = head;
while(p2 != null) {
ListNode tmp = p2.next;
p2.next = p1;
p1 = p2;
p2 = tmp;
}
return p1;
}
}
剑指 Offer 35. 复杂链表的复制
在复杂链表中，每个节点除了有一个
next指针指向下一个节点，还有一个random指针指向链表中的任意节点或者null。
复杂链表的复制难点在于，复制到某一结点时，该random指针所指结点可能还未被创建。所以大致有两种思路：
- 既创建
next所指结点，又创建random所指结点。 - 按
next所指顺序依次创建结点，全部结点创建后再开始random指针的赋值。
方法一：next结点与random结点同时递归生成
利用一Map记录结点的创建情况，若已创建则直接返回，否则创建后更新Map。由于next指针连接了所有节点，故所有节点都会被复制。
class Solution {
Map<Node, Node> createdNode = new HashMap<>();
public Node copyRandomList(Node head) {
if(head == null) return null;
Node neuu = createdNode.get(head);
if(neuu == null) {
neuu = new Node(head.val);
createdNode.put(head, neuu);
neuu.next = copyRandomList(head.next);
neuu.random = copyRandomList(head.random);
}
return neuu;
}
}
方法二：先next，后random（Map映射新旧节点）
同样采用Map记录新旧节点的对应情况。整个过程由两次针对原链表的循环组成。
第一次循环的过程除进行常规链表的复制以外，添加Map键值对，建立由原节点到新节点的映射。
第二次循环通过Map建立新节点之间的random指向关系。
class Solution {
public Node copyRandomList(Node head) {
if(head == null) return null;
Map<Node, Node> m = new HashMap<>();
Node ori = head, last = null;
while(ori != null) {
m.put(ori, new Node(ori.val));
if(ori != head) {
m.get(last).next = m.get(ori);
}
last = ori;
ori = ori.next;
}
m.get(last).next = null;
ori = head;
while(ori != null) {
if(ori.random != null) {
m.get(ori).random = m.get(ori.random);
}
else {
m.get(ori).random = null;
}
ori = ori.next;
}
return m.get(head);
}
}
方法三：先next，后random（新节点暂时插入原节点后）
方法二与方法三并无本质区别，对random指针赋值的基础都是新旧相应结点的映射。
方法二主要由三次链表的遍历组成：
第一次遍历，按照原链表next顺序依次创建新节点，并将新节点插入原链表对应旧结点后，使原链表的长度翻倍。这样做的意义是实现了通过旧结点的next指针访问对应新结点，且原列表的next顺序也没有丢失。
第二次遍历，复制random关系。这一遍历的循环变量仍然会依次被赋值为原链表的各节点，假设某一时刻循环变量指向结点A。则A.next指向新节点，A.random指向原节点的random目标，A.random.next指向新节点random指针待指向的节点。
第三次遍历，将新旧链表分离。
class Solution {
public Node copyRandomList(Node head) {
if(head == null) return null;
for(Node ori = head; ori != null; ori = ori.next.next) {
Node neuu = new Node(ori.val);
neuu.next = ori.next;
ori.next = neuu;
}
for(Node ori = head; ori != null; ori = ori.next.next) {
Node neuu = ori.next;
neuu.random = (ori.random == null)?null:(ori.random.next);
}
Node nhead = head.next;
for(Node ori = head; ori != null; ori = ori.next) {
Node neuu = ori.next;
ori.next = neuu.next;
if(neuu.next != null) neuu.next = neuu.next.next;
}
return nhead;
}
}