链表

Note

注意判断链表为空的情况

while 和if 一样满足条件进入循环

链表操作

链表的移除特定数值有两种方法：

方法1：直接使用原来的链表来进行删除操作。需要通过while保证头节点不是移除节点。

public ListNode removeElements(ListNode head, int val) {
    while (head != null && head.val == val) {
        head = head.next;
    }
    // 已经为null，提前退出
    if (head == null) {
        return head;
    }
    // 已确定当前head.val != val
    ListNode pre = head;
    ListNode cur = head.next;
    while (cur != null) {
        if (cur.val == val) {
            pre.next = cur.next;
        } else {
            pre = cur;
        }
        cur = cur.next;
    }
    return head;
}

方法2：使用虚拟节点。这样头结点和其他节点的移除方式完全一致，少了判断头节点是不是目标节点和头节点为空的情况

public ListNode removeElements(ListNode head, int val) {
    if (head == null) {
        return head;
    }
    // 因为删除可能涉及到头节点，所以设置dummy节点，统一操作
    ListNode dummy = new ListNode(-1, head);
    ListNode pre = dummy;
    ListNode cur = head;
    while (cur != null) {
        if (cur.val == val) {
            pre.next = cur.next;
        } else {
            pre = cur;
        }
        cur = cur.next;
    }
    return dummy.next;
}

707.设计链表

https://leetcode.cn/problems/design-linked-list/description/

思路是：创建一个虚拟头保证一致，设计链表最大的问题就是你不确定什么时候是while（temp.next！=null）还是while（temp！=null）这个逻辑就是判断里边需不需要temp.next.val如果不需要那么就可以temp，这样的话就会多迭代一次迭代一次最后的null。所有的尾端插入都一样，头部插入引入虚拟头之后一样，中间插入要记录上一个节点，删除也要记录上一个节点，

24. 两两交换链表中的节点

解题思路就是画图，并且你要保证改变指针之后不影响后续的操作。然后虚拟节点的作用也是一样，不用单独考虑头节点的情况。步骤之间的顺序你一定要理清楚，如果中间改变了cur-next那原有的链接就会消失。所以最好的做法就是提前保存这些变量。你如果要调换步骤23那么temp= cur->next->next。

class Solution {
  public ListNode swapPairs(ListNode head) {
        ListNode dumyhead = new ListNode(-1); // 设置一个虚拟头结点
        dumyhead.next = head; // 将虚拟头结点指向head，这样方便后面做删除操作
        ListNode cur = dumyhead;
        ListNode temp; // 临时节点，保存两个节点后面的节点
        ListNode firstnode; // 临时节点，保存两个节点之中的第一个节点
        ListNode secondnode; // 临时节点，保存两个节点之中的第二个节点
        while (cur.next != null && cur.next.next != null) {
            temp = cur.next.next.next;
            firstnode = cur.next;
            secondnode = cur.next.next;
            cur.next = secondnode;       // 步骤一
            secondnode.next = firstnode; // 步骤二
            firstnode.next = temp;      // 步骤三
            cur = firstnode; // cur移动，准备下一轮交换
        }
        return dumyhead.next;  
    }
}

还有一个递归的解法比较难以理解，递归的思想就是从后往前倒退。这里我直接画一个迭代的图，每一次递归的都是两个数之后即next->next，所以两次head是1，3。再一次递归会出现null并给3的递归new Node 返回null，

class Solution {
    public ListNode swapPairs(ListNode head) {
        // base case 退出提交
        if(head == null || head.next == null) return head;
        // 获取当前节点的下一个节点
        ListNode next = head.next;
        // 进行递归
        ListNode newNode = swapPairs(next.next);
        // 这里进行交换
        next.next = head;
        head.next = newNode;
        return next;
    }
}

链表相交

面试题 02.07. 链表相交

这个暴力通过两个while循环来做很简单，但是提供一种新思路先确定长度，在根据长度，然后计算两个的差，给长的那个的current加上这个差保证统一长度，这样在一对一的比较就可以很快的找到想找的相交点了。

环形链表

https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html

找到相交点可以通过快慢指针决定。证明如下，找到成环点就是x=z所以再创建另一个节点从起点出发就行了与slow的相交点就是入还点。

总结