【算法第二天7.14】移除链表元素,设计链表,反转链表
链接力扣203-移除链表元素
思路:
1、创建一个虚拟头节点,让头节点与其它节点处理方式相同
2、要移除元素,必须知道移除元素的前一个节点,以便后面连接
3、while循环:cur.next != null的前提是cur != null
java创建节点的构造函数
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();
dummy.next = head;
ListNode cur = dummy;
while(cur != null && cur.next != null){
if(cur.next.val == val){
cur.next = cur.next.next;
}else{
//这里一定是else才往后走,如果有需要移除的元素(if里的语句),
//则不需要往后走,继续处理下一个元素
cur = cur.next;
}
}
return dummy.next;
}
}
链接力扣707-设计链表
思路:主要是搞清楚定义节点和自己定义链表
1、获取链表第index个元素,index的范围0——size-1
2、某个新节点添加(删除)到第index个元素之前,主要先找到index个元素的前驱节点,添加新元素index范围:0-size
3、删除旧元素index范围:0-size-1
// 定义链表节点
class Node{
int val;
Node next;
Node(){};
Node(int val){
this.val = val;
}
Node(int val,Node next){
this.val = val;
this.next = next;
}
}
class MyLinkedList {
// 初始化我自己的链表:长度 和 虚拟头节点
int size;
Node head;
public MyLinkedList() {
size = 0;
head = new Node(-1);
}
public int get(int index) {
// 索引:0——size-1
//如果index非法,返回-1
if (index < 0 || index >= size) {
return -1;
}
Node cur = new Node();
cur = head;
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) {
if(index < 0) index = 0;
// 如果索引大于总长度,则退出
if(index > size) return;
// 链表长度需要增加
size++;
// 找到要插入节点的前驱节点
Node pre = head;
for(int i = 0; i <index; i++ ){
pre = pre.next;
}
Node newnode = new Node(val);
newnode.next = pre.next;
pre.next = newnode;
}
public void deleteAtIndex(int index) {
if(index < 0) return;
// 如果索引大于总长度,则退出
if(index >= size) return;
size--;
// 找到要删除节点的前驱节点
Node pre = head;
for(int i = 0; i <index; i++ ){
pre = pre.next;
}
// 这一段代码已经包含下面index=0的情况了
pre.next = pre.next.next;
// if(index == 0){
// head = head.next;
// return;
// }
}
}
/**
* 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-反转链表
思路:
1、创建一个虚拟节点,让头节点和其它节点操作一样;
2、改变指针的方向,要保存好下一个节点,以防丢失;
3、最后两个反转完,cur指向空了,所以需要返回pre
class Solution {
public ListNode reverseList(ListNode head) {
ListNode dummy = null;
// 只需要创建一个虚拟节点即可,不需要让它指向head
// dummy.next = head;
ListNode pre = dummy;
ListNode cur = head;
while(cur != null){
ListNode tmp = cur.next;
cur.next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
}