链表 - 简书

1、反转链表

    public ListNode reverseLinkedList(ListNode head) {
        ListNode next = null;
        ListNode pre = null;
        while (head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

2、判断单向链表是否有环

2.1、使用HashSet

在遍历过程中，使用一个hashSet集合来保存已经遍历过的节点，在遍历下一个节点的时候，判断这个节点是否在集合中，如果在这个集合中说明出现环了。

2.2、使用快慢指针

使用一个快指针，一个慢指针，快指针一次走两步，慢指针一次走一步，如果链表中有环，那么快指针和慢指针最后会相遇。
还可以继续找到环的入口，相遇之后呢，快指针回到初始节点，一次走一步，那么最后快指针和慢指针最后会在链表环的入口相遇。

    public boolean isLoop(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode fast = head.next.next;
        ListNode slow = head.next;
        while (slow != fast) {
            if (fast == null || fast.next == null || fast.next.next == null) {
                return false;
            }
            fast = fast.next.next;
            slow = slow.next;
        }
        return true;
    }

 //如果没有环，返回null
    //如果有环，返回第一个入环的节点
    public static ListNode getLoopNode2(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }

        ListNode fast = head.next.next; //快指针一次两步
        ListNode slow = head.next; //慢指针一次一步

        while (fast != slow) { 
            if (fast == null || fast.next == null || fast.next.next == null) {  //如果到达链表结束，表示不可能有环
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
        }

        fast = head; //fast回到head，一次只走一步，再次遇到slow，即为入环节点

        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

3、拷贝有随机指针的链表

有随机指针的链表

3.0、使用老节点后新增、处理rand，拆分新旧节点

1、第一遍遍历旧链表、再每个节点后插入新的拷贝的节点，先不管rand

step1

2、第二遍、一次遍历两个节点，为新的拷贝节点处理rand指针

cur.next.rand = cur.rand == null ? null : cur.rand.next;

step2

3、拆分新旧节点

 public Node copyLinkedList(Node head) {
        if (head == null) {
            return null;
        }
        Node cur = head;
        //1、在原来的链表中插入新的节点，1->1'->2->2'->3->3'->null
        while (cur != null) {
            Node next = cur.next;
            cur.next = new Node(cur.val);
            cur.next.next = next;
            cur = next;
        }
        cur = head;
        //2、给新节点添加rand指针
        while (cur != null) {
            cur.next.rand = cur.rand == null ? null : cur.rand.next;
            cur = cur.next.next;
        }
        //3、把新旧节点分离
        Node newHead = head.next;
        Node newTail = head.next;
        cur = head;
        while (cur != null) {
            Node next = cur.next.next;
            cur.next = next;
            newTail.next = next == null ? null : next.next;
            cur = next;
            newTail = newTail.next;
        }
        return newHead;
    }

3.1、使用HashMap

第一遍遍历旧链表，往Map中添加元素，Map的key是原来的节点，value是新的复制节点
第二遍遍历旧链表，根据旧链表的关系，处理新链表的next，rand关系。

    public Node copyLinkedList(Node head) {
        if (head == null) {
            return null;
        }
        HashMap<Node, Node> map = new HashMap<>();
        Node cur = head;
        //1、把原始节点，和拷贝节点放入Map
        while (cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        cur = head;
        //2、处理新的节点的连接关系
        while (cur != null) {
            Node copy = map.get(cur);
            copy.next = map.get(cur.next);
            copy.rand = map.get(cur.rand);
            cur = cur.next;
        }
        return map.get(head);
    }

链表