lc203移除链表元素

思路

使用虚拟头节点以便操作头节点，逻辑判断处注意模拟

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) return head;
        ListNode dummyNode = new ListNode(-1, head);
        ListNode pre = dummyNode, curNode = head;
        while (curNode != null){
            if (curNode.val == val){
                pre.next = curNode.next;
            } else {
                pre = curNode;
            }
            curNode = curNode.next;
        }
        return dummyNode.next;
    }
}

lc707设计链表

思路

不随意操作共享变量，使用while时想好循环次数

代码

class ListNode{
    int val;
    ListNode next;
    ListNode(){}
    ListNode(int val){
        this.val = val;
    }
    ListNode(int val, ListNode next){
        this.val = val;
        this.next = next;
    }
}

class MyLinkedList {

    int size;
    ListNode head;

    public MyLinkedList() {
        size = 0;
        head = new ListNode(0);
    }
    
    public int get(int index) {
        if (index < 0 || index >= size){ return -1; }
        ListNode curNode = head;
        while (index-- >= 0){ curNode = curNode.next; }
        return curNode.val;
    }
    
    public void addAtHead(int val) {
        ListNode newNode = new ListNode(val, head.next);
        head.next = newNode;
        size++;
    }
    
    public void addAtTail(int val) {
        ListNode preNode = head;
        while (preNode.next != null){ preNode = preNode.next; }//此时不可操作共享变量size
        ListNode newNode = new ListNode(val);
        preNode.next = newNode;
        size++;
    }
    
    public void addAtIndex(int index, int val) {
        if (index > size){ return; }//等于size时也可插入
        if (index < 0){ index = 0; }
        ListNode preNode = head;
        size++;
        while (index-- > 0){ preNode = preNode.next; }
        preNode.next = new ListNode(val, preNode.next);
    }
    
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size){ return; }
        size--;
        ListNode preNode = head;
        while (index-- > 0){ preNode = preNode.next; }
        if (preNode.next == null) { return; }
        preNode.next = preNode.next.next;
    }
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */

lc206反转链表

思路

确定最小翻转逻辑

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null, cur = head;
        while (cur != null){
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}