[数据结构与算法]代码随想录算法训练营第三天| 203.移除链表元素、707.设计链表、206.反转链表

前言：之前学习数据结构一直是使用C语言版本，对其中的节点操作以及边界控制把控较为精准，但是采用Java刷题时，对链表操作较为生疏，先对其进行相应总结。

//节点结构
class ListNode {
	int val;
	ListNode next;
	ListNode() {
	}
	ListNode(int val) {
		this.val = val;
	}
	ListNode(int val, ListNode next) {
		this.val = val;
		this.next = next
	}

203.移除链表元素

题目链接：203.移除链表元素

参考文章链接：代码随想录_203.移除链表元素

删除节点的基本逻辑为

	if (p.next.val == val) {
		p.next = p.next.next;
		//如果节点不为空
	} else {
		p = p.next;
	}

主要完成了两种实现方式，带虚拟头结点和不带虚拟头结点。更喜欢设定虚拟头结点的方式，不需要对原头结点进行单独的判断操作。

另，Java语言有自己的内存回收机制，不用自己手动释放在逻辑上被删除的节点。

• 无虚拟头结点
  需要加入判断头结点val的情况，最后head指向第一个节点值不为val的节点处（如果没有，head = null。然后按照删除节点的逻辑，进行遍历链表并删除相应节点。

代码如下：

/**
 * 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 p = head;
        while (p != null && p.val == val) {
            //找到第一个值不为val的节点
            head = p.next;
            p = head;
        }
        while (p != null && p.next != null) {
            //删除值为val的节点
            if (p.next.val == val) {
                p.next = p.next.next;
            } else {
                p = p.next;
            }
        }
        return head;
    }
}

• 虚拟头结点
  申请一个新的节点，新节点的next指针指向head，把新节点当做头结点，且对链表进行操作时，不用对其进行处理。这种实现方式，head和其他节点处于同地位，不需要单独操作，少了很多麻烦。

代码如下：

/**
 * 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 dummyNode = new ListNode(-1, head);
        //申请一个虚拟头结点，dummyNode.next = head;
        ListNode p  = dummyNode;
        
        while (p.next != null) {
            if (p.next.val == val) {
                p.next = p.next.next;
            } else {
                p = p.next;
            }
        }
        return dummyNode.next;//返回真正的头结点
    }
}

707.设计链表

题目链接：707.设计链表

参考文章链接：代码随想录_707.设计链表

花了些时间，也写出了相应的方法，相比较与题解中给出的，会繁琐许多，主要的问题在于，没有想到可以将三种不同添加方法集成到一个当中，做了很多重复的工作。

思路不难，只是需要考虑到很多越界的问题，否则会出很多bug。例如，删除元素要考虑后续元素为空，而不能轻易获取其val等。(疯狂出bug）题解中加入了size元素，使得遍历时有了依据，能更容易控制边界情况，有效抑制了空指针的出现。

通过这一题的训练，能够更好地掌握相应语言对于链表的定义、操作，并熟练应用。

代码如下：

class ListNode {
    int val;
    ListNode next;
    ListNode() {
    }
    ListNode(int val) {
        this.val = val;
    }
}

class MyLinkedList {
    //size存储链表元素个数
    int size;
    //虚拟头结点
    ListNode head;

    public MyLinkedList() {
        //链表初始化
        size = 0;
        head = new ListNode(0);
    }

    //获取第index个节点的值
    public int get(int index) {
        if (index < 0 || index >= size)
            return -1;
        ListNode pre = head;
        for (int i = 0; i < index; i++) {
            pre = pre.next;
        }
        return pre.next.val;
    }
    
    //链头插入元素
    public void addAtHead(int val) {
        addAtIndex(0, val);
    }
    
    //链尾插入元素
    public void addAtTail(int val) {
        addAtIndex(size, val);
    }
    
    //index位置插入元素val
    public void addAtIndex(int index, int val) {
        if (index > size) return;
        if (index < 0) index = 0;

        ListNode temp = new ListNode(val);
        ListNode pre = head;
        //找到要添加位置的前驱结点
        for (int i = 0; i < index; i++) {
            pre = pre.next;
        }
        //添加节点
        temp.next = pre.next;
        pre.next = temp;
        
        //更新结点个数
        size++;
    }
    
    //删除第index个结点
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) return;

        ListNode pre = head;
        for (int i = 0; i < index; i++) {
            pre = pre.next;
        }
        pre.next = pre.next.next;
        //写代码时忘记更新size，出bug
        size--;
    }
}

206.反转链表

题目链接：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 dummyNode = new ListNode(0, null);
        ListNode p = head;//p记录原链表中摘下的节点
        while (head != null) {
            head = head.next;
            p.next = dummyNode.next;
            dummyNode.next = p;
            p = head;
        }
        return dummyNode.next;
    }
}