链表理论基础
- 链表
- 一种通过指针串联在一起的线性结构
- 数据域
- 指针域(存放指向下一个节点的指针,最后一个节点的指针域指向NULL)
- 入口节点——head头节点
- 一种通过指针串联在一起的线性结构
- 链表类型
- 单链表
- 双链表
- 两个指针域
- 一个指向下一个节点
- 一个指向上一个节点
- 两个指针域
- 循环链表
- 首尾相连
- 约瑟夫环问题
- 链表存储方式
- 数组:在内存中连续分布
- 链表:通过指针域的指针链接在内存中的各个节点,散乱分布在内存中的某地址上,分配机制取决于操作系统的内存管理
移除链表元素
public class HelloWorld {
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;
}
}
class Solution {
public ListNode removeElements(ListNode head, int val)
{
if(head==null)
{
return head;
}
//设置虚拟节点
ListNode dummy=new ListNode(-1,head);
ListNode pre=dummy;
ListNode cur=head;
while(cur!=null)
{
if(cur.val==val)
{
pre.next=cur.next;
}
else
{
pre=cur;
}
cur=cur.next;
}
return dummy.next;
}
}
public static void main(String[] args) {
}
}
设计链表
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;
}
}
class MyLinkedList {
//链表元素个数
int size;
//虚拟头节点
ListNode head;
//初始化链表
public MyLinkedList() {
size=0;
head=new ListNode(0);
}
public int get(int index) {
if(index<0||index>=size)
{
return -1;
}
ListNode cur=head;
for(int i=0;i<=index;i++)
{
cur=cur.next;
}
return cur.val;
}
public void addAtHead(int val) {
// 在头节点前面 增加一个节点 == 在第0个元素前添加
addAtIndex(0,val);
}
public void addAtTail(int val) {
// 在最后一个节点 后 增加一个节点 == 在第size+1 个元素添加
addAtIndex(size,val);
}
public void addAtIndex(int index, int val) {
// 在下标为Index的位置前面,增加一个节点
if(index>size)
{
return;
}
if(index<0)
{
index=0;
}
size++;
ListNode pre=head;
for(int i=0;i<index;i++)
{
pre=pre.next;
}
ListNode node=new ListNode(val);
node.next=pre.next;
pre.next=node;
}
public void deleteAtIndex(int index) {
// 删除下标为Index的节点
if(index<0||index>size)
{
return;
}
size--;
if(index==0)
{
head=head.next;
}
else
{
ListNode pre=head;
for(int i=0;i<index;i++)
{
pre=pre.next;
}
pre.next=pre.next.next;
}
}
}
反转链表
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre=null;
ListNode cur=head;
ListNode temp;
while(cur!=null)
{
temp=cur.next;
cur.next=pre;
//更新pre和cur指针
pre=cur;
cur=temp;// cur=cur.next;
}
return pre;
}
}
标签:203,ListNode,cur,val,next,链表,移除,public
From: https://www.cnblogs.com/FreeDrama/p/18403204