套路

• 链表问题有两种解法：1.递归 2. 两根指针

注意点

• 暂无

目录

• 合并两个排序的链表（递归）
• 从尾到头打印链表（递归）
• 删除链表中重复的结点（递归、两根指针）

合并两个排序的链表

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

public ListNode Merge(ListNode list1,ListNode list2) {
    if (list1 == null) return list2;
    if (list2 == null) return list1;
    if (list1.val <= list2.val) {
        list1.next = Merge(list1.next, list2);
        return list1;
    } else {
        list2.next = Merge(list1, list2.next);
        return list2;
    }
}

从尾到头打印链表

输入一个链表，从尾到头打印链表每个节点的值。

• 最优解：递归法是代码量最少的，本题可以用栈实现，而如果不用数据结构的话就可以用递归实现。其实本质上也是用栈实现，只不过栈变成了JVM方法栈。

private ArrayList<Integer> res = new ArrayList<>();
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
    if (listNode != null) {
        printListFromTailToHead(listNode.next);
        res.add(listNode.val);
    }
    return res;
}

删除链表中重复的结点

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

public ListNode deleteDuplication(ListNode pHead) {
    if (pHead == null || pHead.next == null) {
        return pHead;
    }
    if (pHead.val == pHead.next.val) {
        ListNode pNode = pHead.next;
        while (pNode.next != null && pHead.val == pNode.next.val) {
            pNode = pNode.next;
        }
        return deleteDuplication(pNode.next);
    } else {
        pHead.next = deleteDuplication(pHead.next);
        return pHead;
    }
}