203.移除链表元素 (opens new window)

简单题目，主要考察对链表数据结构的熟悉程度。

/**
 * 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 null;
        }

        if(head.val == val){
            head = removeElements(head.next,val);
        }else{
            head.next = removeElements(head.next,val);
        }
        return head;
    }
}

707. 设计链表 (opens new window)

这道题目，主要还是考察链表的结构和虚拟节点头的运用。

但是题目描述的不是很清楚，导致做的时候边界条件不太正确。

后面修改过来了

class MyLinkedList {
    int size;

    ListNode head; //虚拟头节点

    

    public MyLinkedList() {
        this.size = 0;
        this.head = new ListNode(0);
    }

    /**
     * 获取第index个节点
     * @param index
     * @return
     */
    public int get(int index) {
        if (index<0 || index>=size){
            return -1;
        }

        ListNode currentNode = head;
        for (int i=0;i<=index;i++){
            currentNode = currentNode.next;
        }
        return  currentNode.val;
    }
    
    public void addAtHead(int val) {
        addAtIndex(0, val);
    }
    
    public void addAtTail(int val) {
        addAtIndex(size, val);
    }
    
    public void addAtIndex(int index, int val) {
        if (index>size){
            return;
        }
        ListNode currentNode = head;
        for (int i=0;i<index;i++){
            currentNode =currentNode.next;
        }

        ListNode node = new ListNode(val);
        node.next =currentNode.next;
        currentNode.next = node;
        size++;
    }
    
    public void deleteAtIndex(int index) {
        if (index<0 ||index>=size){
            return;
        }
        ListNode  currentNode = head;
        for (int i=0;i<index;i++){
            currentNode =currentNode.next;
        }
        if (currentNode.next!=null){
            currentNode.next = currentNode.next.next;
        }
        size--;
    }
}

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

/**
 * 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);
 */

206. 反转链表 (opens new window)

什么叫做熟悉的默认人题

递归就完事了

/**
 * 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 || head.next == null) {
            return head;
        }
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;

    }
}