1、链表的反转

使用双指针（准确的是三指针记录），分别记录当前，上一节点，下一节点，然后进行反转

    public ListNode reverseList(ListNode head) {
        ListNode p = head, q;
        head = null;
        while (p != null) {
            q = p.next;
            p.next = head;
            head = p;
            p = q;
        }
        return head;
    }

2、相交链表

力扣

• 指针遍历完A再遍历B，到达node和B再遍历a一致都是

a + b - c 的 距离

• 如果AB、重合时有两种情况：
  • A、B 有重合点
  • 无重合点 ，公式中对应C 为 0

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode A = headA, B = headB;
        if (A == null || B==null) return null;
        while (A != B) {
            A = A != null ? A.next : headB; 
            B = B != null ? B.next : headA;
            A = A.next != null ? A.next : headB; // 此类写法无法应对无交点的情况
            B = B.next != null ? B.next : headA;
        }
        return A;
    }

3、环形链表

力扣

思想与上类似，都是采用双指针，进行推到，如果双指针遍历的节点相同，则返回true 本题采用快门指针的思想，初始值都为头节点，慢指针走一步，快指针走两步，如果两个节点相同时则返回true，如果fast节点为空，则说明没有环，返回false

public boolean hasCycle(ListNode head) {
        if (head==null) return false;
        ListNode slow = head, fast = slow; 
        while (true) {
            if (fast==null || fast.next==null) return false;
            slow = slow.next;
            fast = fast.next.next;
            if (fast == slow) return true;
        }
    }
    // public boolean hasCycle(ListNode head) {
 //                if (head==null) return false;
    //     ListNode slow = head, fast = slow.next; //虽然这种赋值也可以，但是无法用公式推导
    //     while (slow != fast) {
    //         if (fast==null || fast.next==null) return false;
    //         slow = slow.next;
    //         fast = fast.next.next;
    //     }
    //     return true;
    // }

4、环形链表 | |

力扣

设fast走的路程 f ，slow的路程 s，头节点导环的起点为 a，环的路程 b

• f = 2s
• f = s + nb

所以 s = nb 令fast节点指向 head，当fast节点走到入口时 走的距离为 a ,slow 的距离 nb + a 所以两节点相遇

public ListNode detectCycle(ListNode head) {
        ListNode fast = head, slow = head;
        while (true) {
            if (fast == null || fast.next == null) return null;
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) break;
        }
        System.out.println(fast.val);
        System.out.println(slow.val);
        fast = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return fast;
    }

4、合并有序链表

力扣

递归

当两个链表有一个为 null 时，就可以视为递归最后一层结束标志 在每一层都有

• list1.next = mergeTwoLists(list1.next, list2);

或者

• list2.next = mergeTwoLists(list1, list2.next);

对两个链表进行连接

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

迭代

分别定义两个辅助节点，

• preHead ： 虚拟头节点记录头节点的位置
• pre ： 记录移动轨迹的辅助节点

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode preHead = new ListNode(-1);
    ListNode pre = preHead;
    while (list1 != null && list2 != null) {
        if (list1.val <= list2.val) {
            pre.next = list1;
            list1 = list1.next;
        } else {
            pre.next = list2;
            list2 = list2.next;
        }
        System.out.println(pre.val);
        pre = pre.next;
    }
    pre.next = list1 == null ? list2 : list1;
    return preHead.next;
}

两数相加

相加过程中需要确认当前位置的数字和下一位需要进位的值，然后连接前后节点

迭代模拟

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int nextVar = 0;
        ListNode preHead = new ListNode(-1); //头节点
        ListNode head = preHead;
        while (!(l1 == null && l2 == null)) {
            int l1var = 0, l2var =0;
            if (l1 != null) {
                l1var = l1.val;
                l1 = l1.next
            }
            if (l2 != null) {
                l2var = l2.val;
                l2 = l2.next;
            } 
            ListNode node = new ListNode((l1var + l2var + nextVar) % 10);
            nextVar = (l1var + l2var+nextVar) / 10;
            //连接前后节点
            head.next = node;
            head = node;
        }
        // 如果最后一位需要进位
        if (nextVar == 1) {
            head.next = new ListNode(nextVar);
        }
        return preHead.next;
    }

递归

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        return add(l1, l2, 0);
    }
    /**
        返回两个链表相加的头部
     */
    public ListNode add(ListNode l1, ListNode l2, int bit) {
        if (l1 == null && l2 == null && bit == 0) {
            return null;
        }
        int val = bit;
        if (l1 != null) {
            val += l1.val;
            l1 = l1.next;
        }
        if (l2 != null) {
            val += l2.val;
            l2 = l2.next;
        }
        ListNode node = new ListNode(val % 10);
        node.next = add(l1, l2, val / 10);
        return node;
    }

两两交换链表中的节点

交换相邻两点，需要注意链表的完整

递归

public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null){ // 递归返回条件
            return head;
        }
        ListNode next = head.next;
         //当前节点的下一个值指向下一层递归，注意参数是next.next
        head.next = swapPairs(next.next);
        next.next = head; //反转
        return next;
    }

迭代+多指针辅助

public ListNode swapPairs(ListNode head) {
    // 如果链表为空或只有一个节点，直接返回
    if (head == null || head.next == null) return head;
    // 新建一个虚拟头结点
    ListNode preHead = new ListNode(-1);
    // p指向虚拟头结点
    ListNode p = preHead;
    // 定义快慢指针，初始值均为头结点
    ListNode fast = head, slow = head;
    // 只要快指针和快指针的下一个节点都不为空，就继续遍历
    while (fast != null && fast.next != null) {
        // 快指针向后移动一位
        fast = fast.next;
        // 定义一个临时节点q，指向快指针的下一个节点
        ListNode q = fast.next;
        // 将快指针的下一个节点指向慢指针
        fast.next = slow;
        // 将慢指针的下一个节点指向临时节点q
        slow.next = q;
        // 将p的下一个节点指向快指针
        p.next = fast;
        // p指向慢指针
        p = slow;
        // 慢指针和快指针均指向临时节点q
        slow = q;
        fast = q;
    }
    // 返回虚拟头结点的下一个节点，即新链表的头结点
    return preHead.next;
}

复制带随机指针的链表

力扣

由于是深度拷贝，因此在拷贝random指针时，需要确定当前random是否被定义，因此无论采用什么方式，基本上都是将next 与 random 分开拷贝。

    public Node copyRandomList(Node head) {
        if (head==null) return head;
        Node cur = head;
        HashMap<Node, Node> nodeMap = new HashMap<>();
        while (cur != null) {
            nodeMap.put(cur, new Node(cur.val)); //key 为老节点，value为新建节点，此时新建节点的next和random都未定义
            cur = cur.next;
        }
        cur = head;
        while (cur != null) {
            nodeMap.get(cur).next = nodeMap.get(cur.next); // map中V.next指向 K.next
            nodeMap.get(cur).random = nodeMap.get(cur.random); //同上
            cur = cur.next;
        }
        return nodeMap.get(head);
    }