目录
一、203.移除链表元素
二、707.设计链表
三、206.反转链表
一、203.移除链表元素
题目链接：203.移除链表元素
题目简述：删除链表中满足Node.val == val的节点。
思路：删除一个节点Node，需要将Node前一个节点的next直接跳过Node，指向Node的下一个节点，这样达到删除的效果。
引入虚拟头节点：在单向链表中，删除节点我们需要知道这个节点的前一个节点，而头节点没有前一个节点，就导致需要分类讨论头节点和非头节点。当引入头节点后，处理方式就一致了，但此时要注意返回节点不再是head了，而是虚拟头节点的next节点。
class Solution {
public ListNode removeElements(ListNode head, int val) {
//创建虚拟头节点
ListNode dummyNode = new ListNode(0);
dummyNode.next = head;
//用pre来遍历链表
ListNode pre = dummyNode;
while(pre.next != null){
if(pre.next.val == val){
pre.next = pre.next.next;
}else{
pre = pre.next;
}
}
return dummyNode.next;
}
}
二、707.设计链表
题目链接：707.设计链表
题目简述：给单向链表或者双向链表完成增、删、改、查功能
以单向链表为例：
链表：创建节点类Node，其中有两个属性，值和下一个节点的地址，分别为int类型的val和Node类型的next，并给Node类添加一个无参构造和有参构造。在每次查询时需要判断是否“越界”，所以需要引入size属性来记录链表的长度，在增加节点时+1，在删除节点时-1。虚拟头节点：增加虚拟头节点可以使在操作头节点和非头节点时一致。
class MyLinkedList {
private class Node{
private int val;
private Node next;
public Node(int val){
this.val = val;
}
public Node(){
}
}
int size;
Node dummyHead;
public MyLinkedList() {
size = 0;
dummyHead = new Node(0);
}
/**
public int get(int index)
public void addAtHead(int val)
public void addAtTail(int val)
public void addAtIndex(int index, int val)
public void deleteAtIndex(int index)
*/
}
增加节点 addAtIndex(int index, int val)：
首先需要判断index是否“越界”，如果没有，再从虚拟头节点处遍历到第index处（链表下标从0开始）；如下图所示，再A和B节点中插入节点C，只需要断开A和B的连接，再增加A和C，C和B的连接。但需注意，应该首先记录下B的信息，因为当A和C连接时，就不能再从A处获得B的信息了；增加节点后对size进行+1操作。
public void addAtIndex(int index, int val) {
if(index < 0){
index = 0;
}
if (index > size)
return;
Node cur = dummyHead;
while(index > 0){
cur = cur.next;
index--;
}
Node node = new Node(val);
node.next = cur.next;
cur.next = node;
size++;
}
在头部增加节点和在尾部增加节点只需将addAtIndex中的index参数设置成0和size，不用再重复编码。
public void addAtHead(int val) {
addAtIndex(0,val);
}
public void addAtTail(int val) {
addAtIndex(size,val);
}
删除节点 deleteAtIndex(int index)：
和增加节点一样需要判断index是否“越界”；从虚拟头节点处顺序遍历到index节点处；如图删除A和C中间的C节点，需要将A节点的next直接指向C即可；删除后对size进行-1操作。
public void deleteAtIndex(int index) {
if(index < 0 || index >=size){
return;
}
Node cur = dummyHead;
while(index > 0){
cur = cur.next;
index--;
}
cur.next = cur.next.next;
size--;
}
查询 int get(int index)
判断index是否“越界”从虚拟头节点开始顺序遍历链表
public int get(int index) {
if(index < 0 || index >=size){
return -1;
}
Node cur = dummyHead.next;
while(index > 0){
cur = cur.next;
index--;
}
return cur.val;
}
三、206.反转链表
题目链接：206.反转链表
题目简述：反转链表
双指针解法：需要创建虚拟头节点，使得操作一致。设置一前一后两个指针，改变后一个指针的next，之后再一起向后移动。
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode cur = head;
ListNode temp = null;
while(cur != null){
//记录cur的原来的next
temp = cur.next;
//反转
cur.next = pre;
//后移
pre = cur;
cur = temp;
}
return pre;
}
}
相关链接
发表评论