代码随想录算法训练营第3天

struct ListNode {
    int val;  // 节点上存储的元素
    ListNode *next;  // 指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
};

public class ListNode {
    int val;  // 结点的值
    ListNode next;  // 下一个结点
 
    public ListNode() {  // 节点的构造函数(无参)
    }
 
    public ListNode(int val) {  // 节点的构造函数(有一个参数)
        this.val = val;
    }
 
    public ListNode(int val, ListNode next) {  // 节点的构造函数(有两个参数)
        this.val = val;
        this.next = next;
    }
}

/**
 * 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) {
        ListNode dummy = new ListNode(-1, head);
        ListNode cur = dummy.next;
        ListNode pre = dummy;
 
        while (cur != null) {
            if (cur.val == val) {
                // delete cur
                pre.next = cur.next;
            }
            else {
                pre = cur;
            }
            cur = cur.next;
        }
 
        return dummy.next;
    }
}

class MyLinkedList {
    class ListNode {
        int val;
        ListNode next;
 
        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
 
    ListNode head;
    ListNode dummy;
    int length;
 
    public MyLinkedList() {
        this.length = 0;
        this.head = null;
        this.dummy = new ListNode(-1, null);
    }
 
    public int get(int index) {
        ListNode cur = this.head;
        if (0 <= index && index <= this.length - 1) {
            for (int i = 0; i < index; i++) {
                cur = cur.next;
            }
            return cur.val;
        }
        else {
            return -1;
        }
    }
 
    public void addAtHead(int val) {
        ListNode tmp;
        if (this.length == 0) {
            tmp = new ListNode(val, null);
        }
        else {
            tmp = new ListNode(val, this.head);
        }
        this.head = tmp;
        this.length ++;
    }
 
    public void addAtTail(int val) {
        this.addAtIndex(this.length, val);
    }
 
    public void addAtIndex(int index, int val) {
        this.dummy.next = this.head;
        ListNode cur = this.dummy.next;
        ListNode pre = this.dummy;
        if (0 <= index && index <= this.length) {
            for (int i = 0; i < index; i++) {
                pre = cur;
                cur = cur.next;
            }
            ListNode tmp = new ListNode(val, cur);
            pre.next = tmp;
            this.length ++;
            this.head = this.dummy.next;
        }
    }
 
    public void deleteAtIndex(int index) {
        this.dummy.next = this.head;
        ListNode cur = this.dummy.next;
        ListNode pre = this.dummy;
        if (0 <= index && index < this.length) {
            for (int i = 0; i < index; i++) {
                pre = cur;
                cur = cur.next;
            }
            pre.next = cur.next;
            this.length --;
            this.head = this.dummy.next;
        }
    }
}

/**
 * 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) {
        if (head != null) {
            ListNode reverse_head = new ListNode(head.val, null);
            ListNode cur = head.next;
            while (cur != null) {
                ListNode tmp = new ListNode(cur.val, reverse_head);
                reverse_head = tmp;
                cur = cur.next;
            }
            return reverse_head;
        }
        else {
            return null;
        }
    }
}