从尾到头打印链表
从尾到头反过来打印出每个结点的值。
- 感觉更优-递归
打123的逆序，先打23逆序再打1，先打3逆序再打2，先打NULL的逆序再打3，出现递归。
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> ret = new ArrayList<>();
if (listNode != null) {
ret.addAll(printListFromTailToHead(listNode.next));
ret.add(listNode.val);
}
return ret;
}
- 链表头插法
将原链表，以头插法的形式，生成新链表，最后输出。
// 头插法构建逆序链表
ListNode head = new ListNode(-1);
//剩余链表
ListNode memo = listNode.next;
//当前要插入的尾指向其对应的头
listNode.next = head.next;
//插入当前值的头
head.next = listNode;
//赋值，准备循环
listNode = memo;
- 栈
栈先进后出，遍历链表入栈，然后出栈生成数组。
在 O(1) 时间内删除链表节点
在 O(1) 时间内删除链表节点
- 链表删除
尾节点，找到前一个结点其next指向null，时间复杂度为O(n)。
不是尾节点，将下一个节点的值赋给该节点，next指向下下一个节点，删除下一个节点，时间复杂度为O(1)。
// 要删除的节点不是尾节点
ListNode next = tobeDelete.next;
tobeDelete.val = next.val;
tobeDelete.next = next.next;
删除链表中重复的结点
删除链表中重复的结点，有一个前置要求，就是升序，且连续。
- 因为有前置要求，所以先判断是否是尾节点。
尾节点，指向null，
不是尾节点，写一个循环，将所有重复节点删除。然后递归该函数。
链表中倒数第 K 个结点
输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。如果该链表长度小于k，请返回一个长度为 0 的链表。
- 优-快慢指针
p1先动，动k个数，然后p1、p2一起动，p1的尾指向null时，p2为头。
while (P1 != null && k-- > 0)
P1 = P1.next;
- 二次循环
第一次循环得出长度。
第二次循环l-n个，得出头节点。
链表中环的入口结点
一个链表中包含环，请找出该链表的环的入口结点。要求不能使用额外的空间。
- 快慢指针
数学题。首先，我们要干两件事。
第一件事，判断有没有环。
第二件事，判断环的起始位置。
第一件事：快指针每次2格，慢指针每次1格，没有碰到null，且相遇，说明有环。
第二件事：当他们相遇时，快指针回到头上，然后继续执行上述操作。再次相遇时，为循环入口。
反转链表
给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。
- 传统的栈解决。
- 双链表，迭代。
简单来说就是头插法。
public ListNode ReverseList(ListNode head) {
ListNode newList = new ListNode(-1);
while (head != null) {
ListNode next = head.next;
head.next = newList.next;
newList.next = head;
head = next;
}
return newList.next;
}
- 递归。
我要输出1-2-3的反向链表，可以先输出2-3的反向再在末尾加1，可以先输出3的反向再在末尾加2。形成递归。在写递归的时候，一定不要思考递归的底层逻辑。将递归抽象出来，思考递归后的结果，在这个结果下，因该怎么做。
public ListNode ReverseList(ListNode head) {
//终止条件
if (head == null || head.next == null)
return head;
//保存当前节点的下一个结点
ListNode next = head.next;
//从当前节点的下一个结点开始递归调用
ListNode reverse = ReverseList(next);
//reverse是反转之后的链表，因为函数reverseList
// 表示的是对链表的反转，所以反转完之后next肯定
// 是链表reverse的尾结点，然后我们再把当前节点
//head挂到next节点的后面就完成了链表的反转。
next.next = head;
//这里head相当于变成了尾结点，尾结点都是为空的，
//否则会构成环
head.next = null;
return reverse;
}
合并两个排序的链表
输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。
- 递归。
A、B两个链表的排序。我先比较它们的第一个数，如果A小，那么我将A之后的链表再和B整合比较，然后返回A即可。出现递归。
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
// list1 list2为空的情况
if(list1 == null || list2 == null){
return list1 != null ? list1 : list2;
}
// 两个链表元素依次对比
if(list1.val <= list2.val){
// 递归计算 list1.next, list2
list1.next = Merge(list1.next, list2);
return list1;
}else{
// 递归计算 list1, list2.next
list2.next = Merge(list1, list2.next);
return list2;
}
}
}
- 双链表，迭代。
感觉就是循环。
public ListNode Merge(ListNode list1, ListNode list2) {
ListNode head = new ListNode(-1);
ListNode cur = head;
while (list1 != null && list2 != null) {
if (list1.val <= list2.val) {
cur.next = list1;
list1 = list1.next;
} else {
cur.next = list2;
list2 = list2.next;
}
cur = cur.next;
}
if (list1 != null)
cur.next = list1;
if (list2 != null)
cur.next = list2;
return head.next;
}
复杂链表的复制
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的 head。
- 双链表，快慢指针。
比较好理解。
- 在每个节点的后面复制一个相同的节点，第一次循环，只赋值基础链表信息。
- 第二次循环，赋值随机链表信息。这步不能在第一次循环做，因为随机链表的下一个指针可能还未赋值。
- 将复制链表分离得出答案。
public RandomListNode Clone(RandomListNode pHead) {
if (pHead == null)
return null;
// 插入新节点
RandomListNode cur = pHead;
while (cur != null) {
RandomListNode clone = new RandomListNode(cur.label);
clone.next = cur.next;
cur.next = clone;
cur = clone.next;
}
// 建立 random 链接
cur = pHead;
while (cur != null) {
RandomListNode clone = cur.next;
if (cur.random != null)
clone.random = cur.random.next;
cur = clone.next;
}
// 拆分
cur = pHead;
RandomListNode pCloneHead = pHead.next;
while (cur.next != null) {
RandomListNode next = cur.next;
cur.next = next.next;
cur = next;
}
return pCloneHead;
}
- Hash表
利用Hash表的映射关系，找到随机链表的具体信息，然后赋值。
- 随机链表的每一个对象，都是独立的。
- 可以用头节点，找到每一个对象。
- 综上，处理链表具体信息的时候，只看链表的具体对象。返回答案的时候，只看头节点。
import java.util.*;
public class Solution {
public RandomListNode Clone(RandomListNode pHead) {
//空节点直接返回
if(pHead == null)
return pHead;
//添加一个头部节点
RandomListNode res = new RandomListNode(0);
//哈希表，key为原始链表的节点，value为拷贝链表的节点
HashMap<RandomListNode, RandomListNode> mp = new HashMap<>();
RandomListNode cur = pHead;
RandomListNode pre = res;
//遍历原始链表，开始复制
while(cur != null){
//拷贝节点
RandomListNode clone = new RandomListNode(cur.label);
//用哈希表记录该节点下的拷贝节点
mp.put(cur, clone);
//连接
pre.next = clone;
pre = pre.next;
//遍历
cur = cur.next;
}
//遍历哈希表
for(HashMap.Entry<RandomListNode, RandomListNode> entry : mp.entrySet()){
//原始链表中random为空
if(entry.getKey().random == null)
entry.getValue().random = null;
else
//将新链表的random指向哈希表中原始链表的random
entry.getValue().random = mp.get(entry.getKey().random);
}
//返回去掉头
return res.next;
}
}
两个链表的第一个公共结点
输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
- 双指针。
和之前环的入口差不多，就是循环。
- p1、p2各走一步，p1先到，则p2回到自己的起点。第二次相遇为公共节点。
- p1、p2各走一步，p1指向null，回到p2的头。p2指向null，回到p1的头。
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
ListNode l1 = pHead1, l2 = pHead2;
while (l1 != l2) {
l1 = (l1 == null) ? pHead2 : l1.next;
l2 = (l2 == null) ? pHead1 : l2.next;
}
return l1;
}
