【leetcode速通java版】03——移除链表元素，设计链表，反转链表-阿里云开发者社区

【leetcode速通java版】03——移除链表元素，设计链表，反转链表

2023-05-27 97

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【leetcode速通java版】03——移除链表元素，设计链表，反转链表

leetcode-T203移除链表元素

解法：

还挺简单的，为了对第一个数据归一化操作，定义头指针，不含数据的虚拟头节点。

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

leetcodeT707 设计链表

class ListNode {
    int val;
    ListNode next;
    ListNode() {
    }
    ListNode(int val) {
        this.val = val;
    }
}
class MyLinkedList {
    int size; //链表的大小
    ListNode head; // 虚拟头节点
    public MyLinkedList() {
        size = 0;
        head = new ListNode(-1);
    }
    public int get(int index) {
        if(index > size - 1 || index < 0) { 
            return -1;
        }
        ListNode cur = head;
        while(index-- >= 0) { // 包含虚拟头结点，所以查找索引为index + 1 的结点
            cur = cur.next;
        }
        return cur.val;
    }
    public void addAtHead(int val) {
    // addAtIndex(0, val);
       ListNode temp = new ListNode(val);
       temp.next = head.next;
       head.next = temp;
       size++;
    }
    public void addAtTail(int val) {
        int index = size - 1;
        ListNode cur = head;
        while(index-- >= 0) {
            cur = cur.next;
        }
        ListNode temp = new ListNode(val);
        cur.next = temp;
        size++;
    }
    public void addAtIndex(int index, int val) {
        if(index > size) {
            return;
        }
        size++;
        if(index == size) {
            addAtTail(val);
            return;
        }
        if(index < 0) {
         // index = 0;
            addAtHead(val);
            return;
        }
        ListNode cur = head;
        while(index-- > 0) { // 找到前一个结点
            cur = cur.next;
        }
        ListNode temp = new ListNode(val);
        temp.next = cur.next;
        cur.next = temp;
    }
    public void deleteAtIndex(int index) {
        if(index < 0 || index > size - 1) {
            return;
        }
        size--;
         ListNode cur = head;
        while(index-- > 0) { // 找到前一个结点
            cur = cur.next;
        }
        cur.next = cur.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);
 */

leetcodeT206 反转链表

/**
 * 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 prev = head;
        if(head == null) {
            return head;
        }
        ListNode cur = head.next;
        while(cur != null) {
            ListNode temp = cur.next;
            cur.next = prev;
            prev = cur;
            cur = temp;
        }
        head.next = null;
        return prev;
    }
}