链表

剑指 Offer 06. 从尾到头打印链表

题解思路1：反转链表

 public int[] reversePrint(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        int size = 0;
        while (cur != null) {
            size++;
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        int[] res = new int[size];
        int i = 0;
        while (pre != null) {
            res[i++] = pre.val;
            pre = pre.next;
        }
        return res;
    }

题解思路2：递归

class Solution {
    ArrayList<Integer> tmp = new ArrayList<Integer>();
    public int[] reversePrint(ListNode head) {
        recur(head);
        int[] res = new int[tmp.size()];
        for(int i = 0; i < res.length; i++)
            res[i] = tmp.get(i);
        return res;
    }
    void recur(ListNode head) {
        if(head == null) return;
        recur(head.next);
        tmp.add(head.val);
    }
}

剑指 Offer 18. 删除链表的节点

题解思路：创建虚拟头节点，删除满足条件的值即可

 public ListNode deleteNode(ListNode head, int val) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == val) {
                pre.next = cur.next;
                return dummy.next;
            } else {
                pre = cur;
                cur = cur.next;
            }
        }
        return null;
    }

剑指 Offer 18.2 删除链表中重复的结点

思路：
初始两个指针：将a指针指向哑节点，将b指针指向head（哑节点的下一个节点）
1、如果a指向的值不等于 b指定的值，则两个指针都前进一位
2、否则就单独移动b，b不断往前走，知道a指向的值不等于b指向的值
注意：这里不是直接比较a.val==b.val，这样比较是不对的，因为初始化的时候，a指向的是哑节点，所以比较逻辑应该是

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode a = dummy;
        ListNode b = head;

        while (b != null && b.next!= null) {
            //初始化时a指向的值为哑节点，所以比较的逻辑应该是a的下一个节点和b的下一个节点
            if (a.next.val != b.next.val) {
                a = a.next;
                b = b.next;
            } else {
                //如果b和a指向的节点是相等的。就不断的移动b，知道b的下一个节点的值不等于为止
                while (b != null && b.next != null && a.next.val == b.next.val) {
                    b = b.next;
                }
                a.next = b.next;
                b =  b.next;
            }
        }
        return dummy.next;
    }
}

剑指 Offer 22. 链表中倒数第k个节点

题解思路1：遍历后取需要的值

public ListNode getKthFromEnd(ListNode head, int k) {
        if (head == null)
            return null;
        ListNode cur = head;
        int count = 1;
        while (cur != null) {
            count++;
            cur = cur.next;
        }

        int target = count - k;
        int i = 1;
        while (i < target) {
            head = head.next;
            i++;
        }
        return head;
    }

题解思路2：双指针

设链表的长度为 N。设置两个指针 P1 和 P2，先让 P1 移动 K 个节点，则还有 N - K 个节点可以移动。此时让 P1 和 P2 同时移动，可以知道当 P1 移动到链表结尾时，P2 移动到第 N - K 个节点处，该位置就是倒数第 K 个节点。

public ListNode getKthFromEnd(ListNode head, int k) {
        if (head == null)
            return null;
        ListNode p1 = head;

        while (p1 != null && k-- > 0) {
            p1 = p1.next;
        }

        if (k > 0)
            return null;
        ListNode p2 = head;
        while (p1 != null) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p2;
    }

剑指 Offer 23. 链表中环的入口结点

public ListNode EntryNodeOfLoop(ListNode pHead) {
    if (pHead == null || pHead.next == null)
        return null;
    ListNode slow = pHead, fast = pHead;
    do {
        fast = fast.next.next;
        slow = slow.next;
    } while (slow != fast);
    fast = pHead;
    while (slow != fast) {
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
}

剑指 Offer 24. 反转链表

public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;

        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }

        return pre;
    }

题解思路2：递归

剑指 Offer 25. 合并两个排序的链表

题解思路1：迭代

  public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy=new ListNode(-1);
        ListNode cur=dummy;
        while(l1!=null&&l2!=null){
            if(l1.val>l2.val){
                cur.next=l2;
                l2=l2.next;
            }else{
                cur.next=l1;
                l1=l1.next;
            }
            cur=cur.next;
        }

        if(l1!=null)
            cur.next=l1;
        if(l2!=null)
            cur.next=l2;

        return dummy.next;
    }

题解思路2：递归

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null)
            return l2;
        if (l2 == null)
            return l1;
        if (l1.val <= l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }

剑指 Offer 35. 复杂链表的复制（链表的深拷贝）

浅拷贝只复制指向某个对象的指针，而不是复制对象本身，新旧对象还是共享同一块内存，但深拷贝会创建一个一模一样的对象，新对象跟原对象不共享内存，修改新对象不会改到原对象。本题的难点是在复制链表的过程中构建新链表各节点的random引用指向。

普通的复制链表的思路

class Solution {
    public Node copyRandomList(Node head) {
        Node cur = head;
        Node dum = new Node(0), pre = dum;
        while(cur != null) {
            Node node = new Node(cur.val); // 复制节点 cur
            pre.next = node;               // 新链表的 前驱节点 -> 当前节点
            // pre.random = "???";         // 新链表的 「 前驱节点 -> 当前节点 」 无法确定
            cur = cur.next;                // 遍历下一节点
            pre = node;                    // 保存当前新节点
        }
        return dum.next;
    }
}

题解思路1：DFS&BFS**
图的基本单元是顶点，顶点之间的关联关系称为边，此题我们可以将链表转换为一个图。

由于图的遍历方式有深度优先搜索和广度优先搜索，同样地，对于此链表也可以使用深度优先搜索和广度优先搜索两种方法进行遍历。

算法：深度优先搜索
从头结点 head 开始拷贝；
由于一个结点可能被多个指针指到，因此如果该结点已被拷贝，则不需要重复拷贝；
如果还没拷贝该结点，则创建一个新的结点进行拷贝，并将拷贝过的结点保存在哈希表中；
使用递归拷贝所有的 next 结点，再递归拷贝所有的 random 结点。

题解思路2：哈希表
利用哈希表的查询特点，考虑构建原链表节点和新链表节点的键值对映射关系，再遍历构建新链表各节点的next和random引用指向即可。
步骤：
1、若头节点head为空节点，直接返回null；
2、初始化，哈希表dic，节点cur指向头节点
3、复制链表：建立新节点，并向dic添加键值对（原cur节点，新cur节点）；cur遍历至原链表的下一节点。
4、构建新链表的引用指向：构建新节点的next和random引用指向，cur遍历至原链表下一节点。
5、返回：新链表的头节点dic[cur]；

public Node copyRandomList(Node head) {
        if (head == null)
            return null;
        Node cur = head;
        Map<Node, Node> map = new HashMap<>();
        //复制各节点，建立原节点与新节点的映射关系
        while (cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        cur = head;
        //构建新链表的next和random指向
        while (cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        //返回新链表的头节点
        return map.get(head);
    }

题解思路3：拆分与拼接
步骤
1、复制各节点，构建拼接链表
2、构建新链表各节点的random指向

当访问原节点cur的随机指向节点cur.random时，对应新节点cur.next的随机指向节点为cur.random.next。

3、拆分原/新链表

 public Node copyRandomList(Node head) {
        if (head == null)
            return null;
        Node cur = head;
        //复制各节点，并构建拼接链表
        while (cur != null) {
            Node tmp = new Node(cur.val);
            tmp.next = cur.next;
            cur.next = tmp;
            cur = tmp.next;
        }

        //构建各新节点的random指向
        cur = head;
        while (cur != null) {
            if (cur.random != null)
                cur.next.random = cur.random.next;
            cur = cur.next.next;
        }

        //拆分两链表
        cur = head.next;
        Node pre = head, res = head.next;
        while (cur.next != null) {
            pre.next = pre.next.next;
            cur.next = cur.next.next;
            pre=pre.next;
            cur=cur.next;
        }
        pre.next=null;//单独处理原链表的尾节点
        return res;//返回结果
    }

剑指 Offer 52. 两个链表的第一个公共节点

题解思路1：双指针
步骤：1、使用两个指针node1、node2分别指向两个链表headA、headB的头节点
2、分别逐节点遍历，当node1到达链表headA的末尾时，重新定位到链表headB的头节点
3、当node2到达链表headB的末尾时，重新定位到链表headA的头节点
4、当他们相遇时所指向的节点就是第一个公共节点

 public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode l1 = headA, l2 = headB;
        while (l1 != l2) {
            l1 = (l1 == null) ? headB : l1.next;
            l2 = (l2 == null) ? headA : l2.next;
        }
        return l1;
    }

题解思路2：set集合解决（慢）
步骤：1、将第一个链表的节点全部存放到集合set当中
2、遍历第二个链表的每一个节点，判断是否存在，如果存在就返回

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> set = new HashSet<>();

        while (headA != null) {
            set.add(headA);
            headA = headA.next;
        }

        while (headB != null) {
            if (set.contains(headB)) {
                return headB;
            }
            headB = headB.next;
        }
        return null;
    }