链表

链表基本操作

1. 从尾到头打印链表
2. 删除链表的节点
3. 链表中倒数第K个节点
4. 反转链表
5. 合并两个有序链表
6. 两个链表的第一个公共节点 Sword52
7. 链表末尾节点的指针指向头结点，形成一个环形链表Sword62：圆圈中最后剩下的数字
8. 节点中除了有指向下一个节点的指针，还有指向前一个节点的指针。Sword36：二叉搜索树与双向链表
9. 节点中除了有指向下一个节点的指针，还有指向任意节点的指针。复杂链表Sword35：复杂链表的复制

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

public Node mergeLinkedList(Node head1, Node head2) {
        if (head1 == null && head2 == null) {
            return null;
        } else if (head1 == null) {
            return head2;
        } else if (head2 == null) {
            return head1;
        } else {
            Node headM = null; // 新链表的头结点
            Node currentM = null; // current结点指向新链表

            if (head1.data < head2.data) {
                headM = head1; // 新链表头结点确定
                currentM = head1; // 当前节点就是头结点
                head1 = head1.next;
            } else {
                headM = head2;// 新链表头结点确定
                currentM = head2;// 当前节点就是头结点
                head2 = head2.next;
            }
            while (head1 != null && head2 != null) {
                if (head1.data < head2.data) {
                    currentM.next = head1; // 当前节点的下一个节点是head1
                    currentM = currentM.next; // 当前节点指针后移
                    head1 = head1.next; // head1指针后移
                } else {
                    currentM.next = head2;
                    currentM = currentM.next;
                    head2 = head2.next;
                }
            }
            if (head1 != null) {
                current.next = head1; // 如果head1还剩下，直接链到最后
            }
            if (head2 != null) {
                current.next = head2; // 如果head2还剩下，直接链到最后
            }
            return headM;
        }
    }

输入一个链表，反转链表后，输出新链表的表头。

        public Node ReverseList(Node head) {
        if (head == null)
            return null;
        // head为当前节点，如果当前节点为空的话，那就什么也不做，直接返回null；
        Node pre = null;
        Node next = null;
        // 当前节点是head，pre为当前节点的前一节点，next为当前节点的下一节点
        // 需要pre和next的目的是让当前节点从pre->head->next1->next2变成pre<-head next1->next2
        // 即pre让节点可以反转所指方向，但反转之后如果不用next节点保存next1节点的话，此单链表就此断开了
        // 所以需要用到pre和next两个节点
        // 1->2->3->4->5
        // 1<-2<-3 4->5
        while (head != null) {
            // 做循环，如果当前节点不为空的话，始终执行此循环，此循环的目的就是让当前节点从指向next到指向pre
            // 如此就可以做到反转链表的效果
            // 先用next保存head的下一个节点的信息，保证单链表不会因为失去head节点的原next节点而就此断裂
            next = head.next;
            // 保存完next，就可以让head从指向next变成指向pre了，代码如下
            head.next = pre;
            // head指向pre后，就继续依次反转下一个节点
            // 让pre，head，next依次向后移动一个节点，继续下一次的指针反转
            pre = head;
            // 不写为head=head.next; 的原因是 head.next 在之前被赋值为了pre，已经不是理解的head.next了
            head = next;
        }
        // 如果head为null的时候，pre就为最后一个节点了，但是链表已经反转完毕，pre就是反转后链表的第一个节点
        // 直接输出pre就是我们想要得到的反转后的链表
        return pre;
    }

https://www.cnblogs.com/smyhvae/p/4782595.html 链表面试题Java实现