代码随想录训练营第3天，开启链表篇章。
203.移除链表元素
题目描述：
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
示例：
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
进入链表篇章，需要明确链表的定义，要自己会写，不然万一面试要手写会直接懵逼。
单链表的定义
/**
* 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; }
* }
*/
解法一：添加虚拟头dummy
class Solution {
public ListNode removeElements(ListNode head, int val) {
if (head == null){
return head;
}
ListNode dummy = new ListNode(-1,head);
ListNode preNode = dummy;
ListNode curNode = head;
while(curNode != null){
if (curNode.val == val){
preNode.next = curNode.next;
}else{
preNode = curNode;
}
curNode = curNode.next;
}
return dummy.next;
}
}
解法二：不添加虚拟头，正常删除
class Solution {
public ListNode removeElements(ListNode head, int val) {
//先判断头节点不为空且需要删除，去掉头节点
while (head != null && head.val == val){
head = head.next;
}
if (head == null){
return head;
}
//此时头节点不等于val，则无须删除；
ListNode preNode = head;
ListNode curNode = head.next;
while(curNode != null){
if (curNode.val == val){
preNode.next = curNode.next;
}else{
preNode = curNode;
}
curNode = curNode.next;
}
return head;
}
}
707.设计链表
题目描述：
你可以选择使用单链表或者双链表，设计并实现自己的链表。
单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。
解法：
class ListNode {
int val;
ListNode next;
//无参构造
ListNode() {}
//有参构造
ListNode(int val){
this.val = val;
}
}
class MyLinkedList {
int size;
ListNode head;
public MyLinkedList() {
this.size = 0;
this.head = new ListNode(0);
}
public int get(int index) {
if (index <0 || index >size) return -1;
ListNode curNode = this.head;
for (int i = 0; i <= index; i++){
curNode = curNode.next;
}
return curNode.val;
}
public void addAtHead(int val) {
addAtIndex(0,val);
}
public void addAtTail(int val) {
addAtIndex(this.size, val);
}
public void addAtIndex(int index, int val) {
if (index >size) return;
if (index < 0){
index = 0;
}
this.size++;
ListNode pre = this.head;
for(int i = 0; i <index; i++){
pre = pre.next;
}
ListNode toAdd = new ListNode(val);
toAdd.next = pre.next;
pre.next = toAdd;
}
public void deleteAtIndex(int index) {
if (index < 0 || index > size) return;
size--;
ListNode pre = this.head;
for (int i = 0; i < index; i++){
pre = pre.next;
}
pre.next = pre.next.next;
}
}
/**
* 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);
*/
206.反转链表
题目描述：
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
解法一：双指针法
解题思路：
将指针的方向反转，由后面一个节点指向前面一个节点
- 设定两个指针，一个指向pre节点，初始状态为null；另一个指向当前节点cur，初始化为head
- 设定指针temp保存当前节点的下一个节点，因为要翻转指针
- 当cur节点不为空时，将cur节点指向pre节点，然后更新pre，cur节点；直到链表走完
/**
* 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;
ListNode temp = null;
while(cur != null){
temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
}
}
解法二：递归法
/**
* 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;
ListNode temp = null;
while(cur != null){
temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
}
}
