链表

203移除链表元素

删除单链表中所有Node.val == val的节点

class Solution {
    public ListNode removeElements(ListNode head, int val) {
		ListNode cur = head;
        ListNode last = null;
        while(cur != null) {
            if(cur == head && cur.val == val) {
                head = head.next;
                cur = head;
                continue;
            }
            if(cur.val == val) {
                last.next = cur.next;
                cur = cur.next;
                continue;
            }
            last = cur;
            cur = cur.next;
            
        }
        return head;
    }
}

本题我的思路是头结点单独处理，但是有一种设置虚拟头结点的方式可以统一操作，具体参见代码随想录 (programmercarl.com)

关于单独处理头结点的过程，代码随想录中的思路比我更好，用一个while一直处理头结点直到头结点不等于val

 while (head != NULL && head->val == val) { // 注意这里不是if
            ListNode* tmp = head;
            head = head->next;
            delete tmp;
 }

707设计链表

206翻转链表

法一：头插法

public ListNode reverseList(ListNode head) {
    if (head == null) {
		return null;
    }
    ListNode temp = null;
    ListNode newhead = null;
    while(head != null) {
        temp = newhead;
        newhead = head;
        head = head.next;
        newhead.next = temp;
    }
    return newhead;
}

法二

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

19删除倒数第k个节点

暴力法很简单，遍历两次链表就可以了，第一次求出链表节点总数

如何只遍历一遍节点？

思路：利用快慢指针，先让快指针走k-1步，即为走到第k个，再让慢指针和快指针同时又以，直到快指针到最后位置，此时慢指针就是倒数k位置

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
		ListNode fast = head;
        ListNode slow = head;
        ListNode pre = null;
        
        
        int count = 0;
        //先让fast走n-1步，同时判断fast是否为null
        while(count < n - 1  && fast != null) {
			fast = fast.next;
            count++;
        }
        //最后fast会走到末尾，slow的位置就是要删除的位置
        while(fast.next != null) {
            pre = slow;
			slow = slow.next;
            fast = fast.next;
        }
        //pre不为空代表上面这个循环进去过，就正常删除slow即可
        if(pre != null) {           
            pre.next = slow.next;
            return head;
        } else if (fast != head) {//针对一共两个节点，删除倒数第二个节点的情况
            head = head.next;
            return head;
        }
        //针对一个节点删除倒数第一个的情况
        return null;
    }
}

可以看到上述方式需要考虑的边界条件很多，不好，因此采用虚拟头结点方式完成此题，可以简化代码

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
		ListNode dummy = new ListNode(0, head);
        ListNode fast = dummy;
        ListNode slow = dummy;
        int count = 0;
        while(count < n  && fast != null) {
			fast = fast.next;
            count++;
        }
        while(fast.next != null) {
			slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return dummy.next;//这样可以兼容两种特殊情况，1是一个节点删除一个，2是两个节点删除倒数第二个
        
    }
}