移除链表元素

203.移除链表元素
本题看上去比较简单，但是容易出错，开始打算只使用一个指向前一节点的指针，但是这样当删除一个节点之后，指针又会指向当前节点，而且在处理尾节点时比较复杂（添加虚拟尾节点一般是在双向链表中），所以本题使用双指针比较方便

/**
 * 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 dummyHead = new ListNode(0,head);
        //建立一个指向当前结点的遍历指针
        ListNode cur = head;
        //建立一个指向前一节点的遍历指针
        ListNode pre = dummyHead;
        while (cur != null) {
            if (cur.val == val) {
                pre.next = cur.next;
            }
            else {
                pre = cur;
            }
            cur = cur.next;
        }
        return dummyHead.next;
    }
}

设计链表

707. 设计链表
本题主要考察对链表的基本操作，需要先定义一个节点类，属性包括val，next，prev，然后MyLinkedList中需要加入虚拟头节点和尾节点以及节点大小，另外在进行节点增加和删除时，只需要一个指向前一节点的指针即可，因为本题找到索引处删除一次就可以了，而上一题需要一直遍历删除，所以需要两个指针

class MyLinkedList {
    
    int size;
    LisNode dummyHead;
    LisNode dummyTail;

    public MyLinkedList() {
        size = 0;
        dummyHead = new LisNode();
        dummyTail = new LisNode();
    }
    
    public int get(int index) {
        if (index < 0 || index >= size) {
            return;
        }
        ListNode cur = dummyHead;
        for (int i=0; i<=index; i++) {
            cur = cur.next;
        }
        return cur.val;
    }
    
    public void addAtHead(int val) {
        addAtIndex(0,val);
    }
    
    public void addAtTail(int val) {
        addAtIndex(size,val);
    }

    public void addAtIndex(int index, int val) {
        //index=size表示加入到尾部
        if (index < 0 || index > size) {
            return;
        }
        LisNode last = dummyHead;
        for (int i=0; i<size; i++) {
            last = last.next;
        }
        size++;
        ListNode newNode = new LisNode(val);
        newNode.next = last.next;
        last.next.prev = newNode;
        last.next = newNode;
        newNode.prev = last;
    }

    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) {
            return;
        }
        LisNode last = dummyHead;
        for (int i=0; i<size; i++) {
            last = last.next;
        }
        size--;
        last.next.next.prev = last;
        last.next = last.next.next; 
    }
}

class LisNode {
    int val;
    ListNode next;
    ListNode prev;

    public ListNode() {

    }

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

    public LisNode(int val, LisNode next, LisNode prev) {
        this.val = val;
        this.next = next;
        this.prev = prev;
    }
}

翻转链表

206.翻转链表
本题使用双指针，一前一后改变指针的方向，但要注意的是如果使用虚拟头结点，容易出现成环的现象，因为dummyHead指向head，反转时head又会指向dummyHead，如果又让dummyHead指向null，那么虚拟头结点也没有意义了，所以本题只要引入一个null节点即可

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