第二章 链表part01

链表理论基础，203.移除链表元素，707.设计链表，206.反转链表 

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 dummy = new ListNode(-1, head);
        ListNode pre = dummy; 
        ListNode cur = head;    // 初始化前节点和当前节点分别为虚拟头结点和头节点
        // 依次遍历
        while (cur != null) {// 退出条件：当前节点为空
            if (cur.val == val) {// 当前节点需要移除，将前节点指向下一个节点
                pre.next = cur.next;
                }
                else {// 不需要移除，继续遍历
                    pre = cur;
            }
            cur = cur.next;
        }
        return dummy.next;
    }
}

707.设计链表

定义结构体时并没有使用虚拟头节点，后续各种操作接口里用了。

记录一下注意点，用虚拟头节点时最后要加一句head = dummyNode.next，因为可能头节点已经被改动了。

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 MyLinkedList {
    // 链表元素个数
    int size;
    // 头节点
    ListNode head;

    // 无参构造方法
    public MyLinkedList() {
        size = 0;
        head = null;
    }

    public int get(int index) {
        // 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 
        if (index < 0 || index > size - 1) {
            return -1;
        }
        ListNode cur = head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        return cur.val;
    }

    public void addAtHead(int val) {
        // 将一个值为val的节点插入到链表中第一个元素之前。
        // 在插入完成后，新节点会成为链表的第一个节点。
        // 虚拟头结点为新节点
        ListNode dummyNode = new ListNode(val);
        dummyNode.next = head;
        // head指向新节点
        head = dummyNode;
        size++;
    }

    public void addAtTail(int val) {
        // 将一个值为 val 的节点追加到链表中作为链表的最后一个元素
        // 虚拟头结点
        ListNode dummyNode = new ListNode();
        dummyNode.next = head;
        // cur遍历 到最后一个元素
        ListNode cur = dummyNode;
        while (cur.next != null) {
            cur = cur.next;
        }
        // 加元素
        cur.next = new ListNode(val);
        size++;
        head = dummyNode.next;
    }

    public void addAtIndex(int index, int val) {
        // 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。
        // 如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。
        // 如果 index 比长度更大，该节点将 不会插入到链表中.
        if (index > size || index < 0) {
            return;
        }
        if (index == size) {
            addAtTail(val);
        } else {
            // 虚拟头结点
            ListNode dummyNode = new ListNode();
            dummyNode.next = head;
            // cur遍历 到index前节点
            ListNode cur = dummyNode;
            for (int i = 0; i < index; i++) {
                cur = cur.next;
            }
            // 加元素
            ListNode toAdd = new ListNode(val);
            toAdd.next = cur.next;
            cur.next = toAdd;
            size++;
            head = dummyNode.next;
        }
    }

    // 如果下标有效，则删除链表中下标为 index 的节点
    public void deleteAtIndex(int index) {
        if (index >= 0 && index < size) {
            // 虚拟头结点
            ListNode dummyNode = new ListNode();
            dummyNode.next = head;
            // pre 遍历至前驱节点
            ListNode pre = dummyNode;
            for (int i = 0; i < index; i++) {
                pre = pre.next;
            }
            // 删除
            pre.next = pre.next.next;
            head = dummyNode.next;
            size--;
        }
    }
}

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 reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur!= null){
            // 存一下下一个节点
            ListNode nex = cur.next;
            // 翻转当前节点指向
            cur.next = pre;
            // 移动指针
            pre = cur;
            cur = nex;
        }
        return pre;
    }
}