链表
- 定义:通过指针串联在一起的线性结构，每一个节点由两个部分组成：数据域和指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null，即为空指针。
链表类型
1. 单链表
2. 双链表
3. 循环链表，即链表首尾相连，可以解决约瑟夫环问题
链表的存储方式
数组在内存中是连续分布的，但是链表在内存中不是连续分布的
链表的定义
public class ListNode {
// 结点的值
int val;
// 下一个结点
ListNode next;
// 节点的构造函数(无参)
public ListNode() {
}
// 节点的构造函数(有一个参数)
public ListNode(int val) {
this.val = val;
}
// 节点的构造函数(有两个参数)
public ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
移除链表元素（力扣203.）
1. 有虚拟节点方式；记得head为val值的边缘条件，以及target指针的空指针问题
/**
* 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 low = new ListNode();
low.next = head;
ListNode target = head;
if(head == null){
return null;
}
while(head.val == val){
head = head.next;
if(head==null){
return head;
}
}
while(target != null){
while(target.val == val){
low.next = target.next;
target = target.next;
if(target == null){
return head;
}
}
low = low.next;
if(target!=null){
target = target.next;}
}
return head;
}
}
- 无虚拟节点方式；先对head指向的值处理，在运行到非val值后扫描后指针
/**
无虚拟节点方式；先对head指向的值处理，在运行到非val值后扫描后指针
*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
//先将head指针处理至不为val值的地方
while(head != null && head.val == val){
head = head.next;
}
//head为空，则直接返回
if(head == null){
return head;
}
ListNode pre = head;
ListNode post = head.next;
while(post != null){
if(post.val == val){
pre.next = post.next;
}else{
pre = post;
}
post = post.next;
}
return head;
}
}
设计链表：实现五个函数（力扣707.）
获取第n个节点的数值
- 使用虚拟头结点的方式 dummynode
- while(n)
- cur = cur.next;
- n--
头部插入节点
- new一个新node
- newNode.next=dummyHead.next;(注意顺序)
- dummyhead.next=newNode;
- size++；
尾部插入节点
- cur = dummyhead；
- while(cur.next == null)
- cur = cur.next;
- cur.next = newNode
第n个节点的插入
- cur应该指向第n个节点的前一个结点
- cur = dummyhead
- while(n)
- cur = cur.next;
- n--;
- newNode.next=cur.next;
- cur.next=newNode;
- size++;
第n个节点的删除
- 判断n的合法性
- cur= dummyhead;
- while(n)
- cur = cur.next;
- n--;
- cur.next=cur.next.next;
- return dummyhead.next;
class ListNode{
int val;
ListNode next;
ListNode(){}
ListNode(int val){
this.val = val;
}
}
class MyLinkedList {//带有头结点的链表
//容量大小
int size;
//虚拟头结点
ListNode dummyhead;
public MyLinkedList() {
//初始化单链表
size = 0;
dummyhead = new ListNode(0);
}
public int get(int index) {
if(index < 0 || index >= size){
return -1;
}
ListNode current = dummyhead;
while(index >= 0){
current = current.next;
index --;
}
return current.val;
}
public void addAtHead(int val) {
ListNode current = dummyhead;
ListNode target = new ListNode(val);
target.next = current.next;
current.next = target;
size++;
}
public void addAtTail(int val) {
ListNode current = dummyhead;
while(current.next != null){
current = current.next;
}
ListNode target = new ListNode(val);
target.next = null;
current.next = target;
size++;
}
public void addAtIndex(int index, int val) {
if(index < 0 || index >= size + 1){
return;
}
ListNode current = dummyhead;
while(index > 0){
current = current.next;
index--;
}
ListNode target = new ListNode(val);
target.next = current.next;
current.next = target;
size++;
}
public void deleteAtIndex(int index) {
if(index < 0 || index >= size){
return;
}
ListNode current = dummyhead;
while(index > 0){
current = current.next;
index--;
}
current.next = current.next.next;
size--;
}
}
/**
* 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.）
- 遍历数组＋头插法
/**
* 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 pummyhead = new ListNode();
// pummyhead.next = head;
if(head == null){
return null;
}
ListNode from = head.next;
ListNode targetPummyHead = new ListNode();
ListNode current = targetPummyHead;
while(head != null){
head.next = targetPummyHead.next;
targetPummyHead.next = head;
head = from;
if(from != null){
from = from.next;
}else{from = null;}
}
return targetPummyHead.next;
}
}
- 双指针写法
- 初始化：cur = head;pre=null;
- 遍历链表：while(cur != null)
- 需要一个临时指针temp = cur.next
- cur.next=pre;
- pre=cur;
- cur=temp
- return pre;
class Solution {
public ListNode reverseList(ListNode head) {
//双指针思路
//初始化
ListNode pre = null;
ListNode cur = head;
while( cur != null){
ListNode temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
}
}
- 递归算法
- reverse(cur,pre){
- if(cur == null)return pre;//此时终止
- temp = cur.next;
- cur.next=pre;
- reverse(temp,cur)}
- //使用：return reverse（head,null);
其实内核解法与双指针解法相同
class Solution {
public ListNode reverseList(ListNode head) {
return reverse(null,head);
}
public ListNode reverse(ListNode pre,ListNode current){
if(current == null){
return pre;//递归的终止条件为current为null
}
ListNode temp = current.next;//临时节点暂存
current.next = pre;
return reverse(current,temp);
}
}