Day03：链表part01：链表理论基础、203.移除链表元素、 707.设计链表、206.反转链表

之前index.php/tags-41973.html" >���博客：https://blog.csdn.net/weixin_43303286/article/details/131720323

链表理论基础

这里记一下java定义链表的方式：

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; }}

跟cpp差不多，就是cpp是struct，而且构造函数有点不一样

203. 移除链表元素

时时刻刻记得把箭头改成点！！！并且移除链表元素的时候应该记录待删除节点的前一个节点：

class Solution {    public ListNode removeElements(ListNode head, int val) {        ListNode dummy = new ListNode();        dummy.next = head;        ListNode p = dummy;        while(p.next != null){            if(p.next.val == val){                p.next = p.next.next;            }else {                p = p.next;            }        }        return dummy.next;    }}

707.设计链表

跟cpp的逻辑一样的，在里面声明一个内部类，以及虚拟头节点进行操作。

class MyLinkedList {        class ListNode {            int val;            ListNode next;            ListNode() {            }            ListNode(int val) {                this.val = val;            }            ListNode(int val, ListNode next) {                this.val = val;                this.next = next;            }        }        private int _size;        private ListNode _dummy;        public MyLinkedList() {            _size = 0;            _dummy = new ListNode(-1, null);        }        public int get(int index) {            if(index = _size){                return -1;            }            ListNode p = _dummy.next;            while(index > 0){                index--;                p = p.next;            }            return p.val;        }        public void addAtHead(int val) {            ListNode p = new ListNode(val, null);            p.next = _dummy.next;            _dummy.next = p;            _size++;        }        public void addAtTail(int val) {            ListNode p = new ListNode(val, null);            ListNode cur = _dummy;            while(cur.next != null){                cur = cur.next;            }            cur.next = p;            _size++;        }        public void addAtIndex(int index, int val) {            if(index  _size){                return;            }            ListNode p = new ListNode(val, null);            ListNode cur = _dummy;            while(index > 0){                index--;                cur = cur.next;            }            p.next = cur.next;            cur.next = p;            _size++;        }        public void deleteAtIndex(int index) {            if(index = _size){                return;            }            ListNode cur = _dummy;            while(index > 0){                index--;                cur = cur.next;            }            cur.next = cur.next.next;            _size--;        }    }

206. 反转链表

没啥好说的，递归法还是不会：

class Solution {    public ListNode reverseList(ListNode head) {        ListNode pre = null;        ListNode cur = head;        while(cur != null){            ListNode tmp = cur.next;            cur.next = pre;            pre = cur;            cur = tmp;        }        return pre;    }}