203. 移除链表元素 707 设计链表 206 反转链表

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

203. 移除链表元素

203. 移除链表元素 707 设计链表 206 反转链表_数据结构

此题需要哨兵节点注意边界即可，很简单不多概述。

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

203. 移除链表元素 707 设计链表 206 反转链表_链表_02

707. 设计链表

203. 移除链表元素 707 设计链表 206 反转链表_数据结构_03

熟悉链表的删除和增加此题不难，我忽略了size++，浪费了半天时间

class MyLinkedList {
    int size;
    ListNode headA;
    public MyLinkedList() {
        size = 0;
        headA = new ListNode(-1,null);
    }
    
    public int get(int index) {
       
        if(index < 0 || index >= size){
            return -1;
        }else{
             ListNode l1 = headA;
            while(index >= 0){
                l1 = l1.next;
                index--;
            }
            return l1.val;
        }
    }
    
    public void addAtHead(int val) {
        addAtIndex(0,val);
        
    }
    
    public void addAtTail(int val) {
        ListNode l1 = headA;
        ListNode temp = new ListNode(val,null);
        while(l1.next != null){
            l1 = l1.next;
        }
        l1.next = temp;
        size++;
    }
    
    public void addAtIndex(int index, int val) {
        if(index > size) return;
        if(index == size){
            addAtTail(val);
            return;
        }
        ListNode temp = new ListNode(val,null);
        if(index <= 0){
            temp.next = headA.next;
            headA.next = temp;
        }else{
            ListNode l1 = headA;
            while(index > 0){
                l1 = l1.next;
                index--;
            }
            temp.next = l1.next;
            l1.next = temp;
        }
        size++;
    }
    
    public void deleteAtIndex(int index) {
        ListNode l1 = headA;
        ListNode l2 = headA.next;
        if(index >= 0 && index < size){
            while(index > 0){
               index--;
               l1 = l2;
               l2 = l2.next;
            }
            l1.next = l2.next;
            size--;
        }
        
    }
}

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

203. 移除链表元素 707 设计链表 206 反转链表_剑指offer_04

206 反转链表

203. 移除链表元素 707 设计链表 206 反转链表_数据结构_05

203. 移除链表元素 707 设计链表 206 反转链表_递归_06

递归法，剑指offer原题

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