Leetcode 707.设计链表

力扣传送门(opens new window)

题意：

在链表类中实现这些功能：

• get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
• addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
• addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
• addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
• deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

解题思路：

1. ListNode 类定义了一个链表节点的结构，包含一个整数值 val 和一个指向下一个节点的指针 next。
2. MyLinkedList 类是自定义的链表类，其中的成员变量包括链表的长度 size 和头节点 head。构造函数中，初始化链表长度为0，并创建一个值为-1的虚拟头节点。
3. get(int index) 方法用于获取链表中指定索引处节点的值。首先检查索引是否越界，如果越界则返回-1。然后通过遍历链表找到对应索引的节点，并返回节点的值。
4. addAtHead(int val) 方法在链表头部插入一个新节点。实际上是调用 addAtIndex(0, val) 方法，在索引0处插入节点。
5. addAtTail(int val) 方法在链表尾部插入一个新节点。实际上是调用 addAtIndex(size, val) 方法，在索引为链表长度的位置插入节点。
6. addAtIndex(int index, int val) 方法在链表的指定索引处插入一个新节点。首先判断索引是否合法，如果大于链表长度，则不进行插入操作；如果小于0，则将索引设置为0。然后通过遍历链表找到插入位置的前一个节点，创建一个新节点，并将新节点的 next 指针指向当前节点的 next 节点，再将当前节点的 next 指针指向新节点，完成插入操作。
7. deleteAtIndex(int index) 方法删除链表中指定索引处的节点。首先判断索引是否越界，如果越界则不进行删除操作。如果要删除的是头节点（即索引为0），则将头节点指向下一个节点，完成删除操作。否则，通过遍历链表找到要删除节点的前一个节点，将前一个节点的 next 指针指向要删除节点的下一个节点，完成删除操作。

代码实现：

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

class MyLinkedList {
    int size = 0;
    ListNode head;
  
    public MyLinkedList() {
        size = 0;
        // 创建一个虚拟头节点
        head = new ListNode(-1); 
    }
  
    public int get(int index) {
        if(index < 0 || index >= size){
            // 如果索引越界，则返回-1
            return -1; 
        }
        ListNode curr = head;
        for(int i = 0 ; i <= index; i++){
            // 遍历链表，找到对应索引的节点
            curr = curr.next; 
        }
        // 返回节点的值
        return curr.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; 
        }
        if(index < 0){
            // 如果索引小于0，则将索引设置为0
            index = 0; 
        }
        // 链表长度加1
        size++; 
        ListNode curr = head;
        for(int i = 0; i < index; i++){
            // 遍历链表，找到插入位置的前一个节点
            curr = curr.next;
        }
        // 创建新的节点
        ListNode currNode = new ListNode(val); 
        // 将新节点的next指针指向当前节点的next节点
        currNode.next = curr.next; 
        // 将当前节点的next指针指向新节点，完成插入操作
        curr.next = currNode; 
    }
  
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) {
            // 如果索引越界，则不进行删除操作
            return; 
        }
        size--; // 链表长度减1
        if(index == 0){
            // 如果要删除的是头节点，则将头节点指向下一个节点
            head = head.next; 
            return;
        }
        ListNode pre = head;
        for(int i = 0; i < index; i++){
            // 遍历链表，找到要删除节点的前一个节点
            pre = pre.next; 
        }
        // 将前一个节点的next指针指向要删除节点的下一个节点，完成删除操作
        pre.next = pre.next.next; 
    }
}