删除相关

203.移除链表元素

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        //设置虚拟头结点，可以将头节点和其他节点同等对待
        ListNode virtualNode = new ListNode();
        virtualNode.next = head;
        ListNode idx = virtualNode;
        while(idx.next != null){
            if (idx.next.val == val){
                idx.next = idx.next.next;
            }else{
                idx = idx.next;
            }
        }
        return virtualNode.next;
    }
}

237. 删除链表中的节点

class Solution {
    public void deleteNode(ListNode node) {
        //既然不能先删除自己，那就把自己的值变成儿子，再把儿子的位置让给孙子
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

19.删除链表的倒数第N个节点

//正常版本很好过，如何一遍解决呢？
//快慢指针
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode hair = new ListNode(0, head);
        ListNode fast = head;
        ListNode slow = hair;
        for (int i = 0; i < n; ++i){
            fast = fast.next;
        }
        while (fast != null){
            fast = fast.next;
            slow = slow.next;
        }
        //此时slow已经到了倒数第n个节点的前一个节点
        slow.next = slow.next.next;
        return hair.next;
    }

反转相关

206. 反转链表

//先添加一个节点不用进行非空判断
//这其实直接把这个链表断开了，用两个指针分别指向两段链表
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null; //用来遍历从null到尾节点
        ListNode curr = head; //用来遍历从头结点到null
        while (curr != null) {
            ListNode temp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = temp;
        }
        return prev;
    }
}

92. 反转链表 II

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        //设置虚拟头结点是这类问题的一般做法
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        //找到待反转区域的前一个节点
        ListNode pre = dummyNode;
        for (int i = 1; i < left; ++i){
            pre = pre.next;
        }
        ListNode cur = pre.next;
        ListNode temp;
        for (int i = left; i < right; ++i){ 
            //这里为什么是right呢，因为五个节点只需要移动四次就可以了
            //即left到right-1
            temp = cur.next;
            //注意赋值顺序，画个图
            cur.next = temp.next;
            temp.next = pre.next;
            pre.next = temp;
        }
        return dummyNode.next;
    }
}

234. 回文链表

交换相关

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

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummyNode = new ListNode();
        dummyNode.next = head;
        ListNode temp = dummyNode;
        while(temp.next != null && temp.next.next != null){
            ListNode node1 = temp.next;
            ListNode node2 = temp.next.next;
            temp.next = node2;
            node1.next = node2.next;
            node2.next = node1;
            temp = node1;
        }
        return dummyNode.next;
    } 
}

25. K 个一组翻转链表

class Solution {
        public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummyHead = new ListNode();
        dummyHead.next = head;
        int size = 0;
        ListNode cur = head;
        while(cur != null){
            cur = cur.next;
            size ++;
        }
        int quotient = size / k;
        ListNode headK = dummyHead;
        cur = headK.next;
        ListNode temp;
        for (int i = 0; i < quotient; ++i){ //要反转几次
            for (int j = 0; j < k-1; ++j){ //本次反转要反转几个节点，这里应该是移动几个节点而不是反转几个节点
                //这个k-1很重要
                temp = cur.next;
                cur.next = temp.next;
                temp.next = headK.next;
                headK.next = temp;
            }
            headK = cur;
            cur = cur.next;
        }
        return dummyHead.next;
    }
}